hey Nick, welcome to the board
changed your MM to mm, no biggie, it�s a trademanrk thang. just wanted ya to know why your post shows as edited by jer.
can�t help much with accomm. advice since i only spent the day in gibraltar and when we went to andorra last winter, it was on a ski trip run by the town hall of madrid and we stayed at a hotel in andorra la vella. hotel was called "hotel salvia" (you can google it and you will get tons of results). it was ok but would have liked to have had a jacuzzi (great for post-skiing

).
one bit of advice i can give you is DON'T BOTHER WITH "caldea". it is a spa there but is hugely overrated. maybe it was due to the fact that when we went it wos a group night and very crowded but the water was lukewarm and the place was overall not very impressive (in my opinion).
we took a chartered bus to andorra as it was included in the trip package and it was 8.5 hours (ish).
i guess transportation would depend upon where your base of operations will be here in spain but i am pretty sure the bus is the best choice.
as for gibraltar, i would take a bus to "la linea de la concepci�n" (aka "la linea") which is the border town on the spain side and walk into gibraltar. it is a very easy walk and you will get in a LOT faster than if you are on a bus or in a car as loooooooooooooong automobile lines tend to form at the border.
saludos,
jer...