Knowing what I know (having been to both), I would certainly not skip the day trips to Segovia and Toledo. Both are fantastic smaller cities. We stayed in the Parador in Toledo, which is great. Segovia is really worth it -- the cathedral, the aqueduct, and the Alcazar (where much of the movie Camelot was filmed). Toledo also has great history.
Barcelona -- agree on le Meridien. Great location on Las Ramblas.
Sevilla -- my favorite city in Spain, the Starwood Alfonso XIII is by far the best choice.
Madrid -- we stayed at the Intercontinental. It was okay, but if I had it to do over again (and had not been trying to use up some Intercontinental free nights) I would have probably stayed at the Westin.
Have not been to Mallorca, so I cannot comment on that.
Granada and the Alhambra are definitely worth seeing, as well as Cordoba. You might think about trying to fit in an overnight in Granada, and stay at the Parador inside the Alhambra -- which is really special.
Congrats and good luck.