You could throw Seville into the mix, it's good, too. If I had to pick a birthday destination, I'd choose Granada, for no reason other than it sounds coolest to me. I've been to Spain, but besides Madrid, not to any of the places on your list, so I can't make a rational comparison.
For train info, you can check out the german national train site,
www.diebahn.de, I think (google it, it'll come up), click for English, and you can get train info anywhere in Europe. It doesn't have pricing or ticketing outside of Germany, but it's a good schedule planner. If you can find yourself a copy of the Thomas Cook European Time Table, that's a good resource, for schedule info, too.