I've recently completed Colosseum and am currently playing XD (Literally, I have the game open right now).
Colosseum is decent if you get a team early on and stick to it. If you try to purify every pokemon as you capture them, you will never have a team as you will always capture shadow pokemon at a faster rate that you purify them, which means that you'll be Shadow Rush-ing your way through the entire game and your pokemon won't level up. It's a boring and tedious way to play the game. XD fixed this problem, as not only does purification work a lot faster, but it can even be done passively without having the pokemon in your team. This changes alone makes XD a much better game than Colosseum for me.
I didn't really care for the plot, it's different from the formula but I didn't think it was better or worse than usual. However, people speak of "edge", and I really don't see it. "Muh darkness" isn't edge and the villains are completely silly (Pic related).
There's clearly a lot of thought put behind the double battles, since a lot of enemies have combos made for double battles, and most of the pokemon you capture have movesets with moves that allow for combos in double battles (Especially in Colosseum).
However, the one big flaw in both games is that the battles take forever.
There are no wild battles, every battle is a trainer battle.
Most trainers have 3 or 4 pokemon.
Eerything is a double battle.
The animations are very well-down; but unfortunately also very long.
All of the above combined means that battles take forever despite few turns actually taking place.
Just the start of the battles take around 20 seconds every time just for both trainers to send out their pokemon, and each turn takes around 30 seconds of animation. I literally browse /vp/ during battles because shit is so long. This shit takes longer than Pearl and Diamond battles.