Great, Mallorca is beautiful and you'll definitely be glad to have a car there. It would be difficult to see a lot of what the island has to offer without one.
As far as Granada vs. Valencia, it's been a long time since I've been to Granada. The one thing Granada has that is unmatchable is the Alhambra, which is spectacular and especially for somebody who enjoys history and architecture. Valencia also has some fantastic architecture, but on the other end of the spectrum, the modern Ciudad de las Artes y las Ciencias by Santiago Calatrava. You'll certainly enjoy either location.
Potentially I would only do one of Toledo and Segovia, or at least leave yourself that option. Since it's your honeymoon, you might be feeling like a chillout day a few days after Mallorca. If you only pick one, I'd opt for Toledo. I'm partial to it, but I just think it's more of a can't miss, and it's also just 25 minutes by train from Madrid.
As far as hotels, I'm mainly SPG and Marriott, with some Melia mixed in, so I can't help on most of the chains you named. I have stayed at Starwood properties (and others) in all the cities named with the exception of Granada, so here are my thoughts:
The Alfonso XIII in Sevilla is one of my favorite hotels ever. I also thought it expensive, and ended up using American Advantage miles - there was a special as Platinum it only cost like 17 or 18,000 miles for a night and at the time I had several hundred thousand miles. I was upgraded to a massive and exquisite corner suite.
In Mallorca if you want to splurge there's a St. Regis. There are two other SPG properties, both a few miles inland with a golf course on the property. I stayed at the Castillo Hotel Son Vida (a Luxury Collection). It's in an old castle, with great historic charm, a nice pool and nice scenery, though if you want your hotel to be on the beach, it's not.
In Madrid, the Westin Palace is a grande dame type hotel, and as central as you can get. It's across the street from the Prado and the Thyssen museums, and a short walk from the Reina Sofia museum, the train station and other tourist spots such as the Parque del Retiro and the Plaza Mayor.
In Barcelona, the Le Meridien is actually one of my favorites. I've gotten great upgrades and SPG Platinum status recognition, and I like being right in the center of the city. But if you want to be on the beach, the W is a wonderful hotel with "wow" views. For a lot fewer points, there is also a Four Points by Sheraton which is perfectly fine.
The Westin Valencia is a beautiful hotel, with modernist style from 1917 and a lovely interior courtyard. But if you are going to pick someplace to not use your Starwood points, I'd say here (or Mallorca if you aren't splurging on St Regis/want to stay on the beach). It's a great hotel but the options in Sevilla, Barcelona and Madrid are superior.