I agree. If you have money, trains are the best bet. I suggest you travel to Madrid, sightsee, rest and then take the AVE down to Sevilla. Went over xmas and it cost me 107eu two ways (its 67 one way, 20% discount for return). If not, buses cost about 35-40eu round trip, but its like 6 hours! i did that the year before. if youre broke its a good option.
While you're in madrid, i suggest you check out this cool program called Englishtown, which allows you to live in English villages for 7 day periods if you agree to converse with their Spaniash clients who go up to practice with "the real deal" - meaning people like you and me, and not teachers! it was a great cultural week (there are activities and an entertainment director and the whole shebang..) and they're always lookign for willing volunteers. Check it out, www.vaughanvillage.com - you sign up online. it a good break between travels!
You can bye train tickets in http://www.renfe.es/ The AVE goes from Barcelona- Zaragoza- Madrid- Sevilla, but it's expensive. The bus is cheaper, but it's less comfortable. You too can go on cheaper trains (no AVE) and make another travel through the coast: Valencia -Murcia... thebus companies are a lot a i can't help you with them. Don't travel into Spain in summer (too hot) nor in winter (too cold), the best time is in spring.
any where near gibraltar is quite warm even in winter . i'm 40 mins away and today was sunny it's has a couple of little showeres but thats it. try staying in some of the caves,and little villages.
Information on the Spanish railway network: www.renfe.es
Apart from using the train you could always check out http://www.vueling.es, I got a return flight from Madrid to Barcelona for 45 Euro and it also saves you a lot of time.
Trains in Spain aren't exactly 21st century, they are comfortable, but boy are they slow. Buses are usually quicker. The only high speed train is between madrid and seville called the AVE and that is expensive. However, (watch this for some logic) there are some trains that are not called the AVE, that run on the same tracks, and sometimes use the AVE carriages, but are cheaper. (No, i don't understand either). Check out the website if you want times and stuff http://www.renfe.es/ but don't try and buy on the web, you can't, unless you have registered and gone to a train station and filled in a form and shown your id and....etc in other words more difficult than buying an airline ticket to the USA! there is also a great easy website for train times in general, but doesn't do prices: http://reiseauskunft.bahn.de/bin/query.exe/en. This does pretty much everywhere in Europe.
I come from London, and I personally think that although there are some tossers on the roads in spain who think it's cool to drive up your arse at 160km per hour and flash their lights at you and not wear a seatbelt, it ain't as difficult as everyone says it is. so long as you know how to drive carefully, you can drive without too many problems. Just keep an eye on the mirrors (all of them). Also small streets, one way systems, hell we get those in the UK and that doesn't stop you. Even if you do go the wrong way. No-one cares enough to fuss, and if they beep the horn, hell spanish drivers do that anyway!
The cheapest hire company i know is http://www.hispacar.com. Try them out.
I live in Seville and know Andalucia pretty well if you got any questions and want to know stuff just ask. Oh and there's some info on restaurants and bars on me website.
[ Edit: sorry, no promos in the forum please. ]