セビージャ

私は以下の日程でアンダルシアをまわったことがあります。

マドリード→セビージャ（1泊）→マラガ（1泊）ミハス日帰り→グラナダ（2泊）→コルドバ（1泊）→バルセロナ

マラガに特別こだわりがないようでしたら、断然セビージャをおすすめします。街並み、雰囲気が素晴らしく、一番スペインを感じられる街だと個人的には思います。

マラガではなくセビージャにすると以下のようになるかと。
コルドバ（1泊）→グラナダ（2泊）サロブレーニャ日帰り→セビージャ（1泊）OUT