Ok what's your time frame .. That's an awfully big schedule ( Maybe not by OZ standards haha ) . As mentioned in a previous post , I would recommend trains over flying because you're delivered straight into the heart of the city you're visiting . The fares can be expensive .. my recent trip to Malaga and back to Madrid was €125 .... but it was worth it !! The trains are superb . Seville -Lisboa is definitely a flight option as is Lisboa-Barcelona .
The high speed rail links ( 290kph ! ) connect Madrid with Granada , Sevilla , Malaga , BArcelona , Cordoba etc..... The state rail company "Renfe" has a website in English ....
http://horarios.renfe.es/hir/ingles.html ... problem is ( if you don't speak Spanish ) that the booking on-line is all in Spanish .
Anymore info and I'll pass it on . Steve