We stayed at the Palace and were very happy with the Starwood cash and points deal. $90 and 4800 pts per night as I recall. Loved the free espresso and IHT on the club floors (top two floors, be sure to ask for these). Super location near Prado.

But, no pool.

Check out the very famous (no kidding, the stained glass is amazing) dining room.