Easter is April 1 (no fooling) so Semana Santa is the last week in March. Feria in Sevilla typically begins 2 weeks after Easter. There's a horse fair in Jerez and a patio fair in Cordoba, both are tail-end of April or beginning of May.
My suggestion is into Sevilla and out of Malaga (works in the opposite order too). If you can't get flights in/out of Sevilla (it's a small airport), Madrid is convenient.
Cordoba is my favorite Spanish city (Toledo might be second). There's a lot to explore and it's well worth a couple nights if not more. It's quieter and smaller than Sevilla (3 nights). Pick up a car, 2-4 nights exploring the pueblos blancos. I used Ronda as a base and drove around exploring the villages. I'd rather drive than change locations. The roads are easy to drive (though it can be pretty tricky driving in some of the villages themselves) and scenic with pull-outs to admire the views and take photos. Then 1-2 nights in Antequera will allow you time to visit the "pink lagoon" (there should be lots by April, there weren't a lot when I went in February, only a couple hundred) and time to hike in El Torcal. Antequera itself is interesting and there are prehistoric dolmens just outside the town. Then Granada and drop the car. Some folks love Granada, others not so much (I'm in the latter category). I spent 4 nights and felt 3 would have been enough. One full day and one evening for the Alhambra, one more day for the city's sights - Albaicin, cathedral, Moroccan market . . . Then 2-3 nights in Malaga, a pretty town with Roman ruins, interesting museums, and a beach, though the water will probably still be pretty cold in April. Can you make it 3 weeks? Even though these places are not small villages, the historic centers are small and enjoyable.
For the Andalucian experience - go to a horse show at the Royal Stables in Cordoba (several evernings a week) and/or at the Royal Equestrian School in Jerez as day trip from Sevilla by train (2-3 late morning shows a week), see fflamenco at the Casa de Flamenco in Sevilla, and tapas, tapas, tapas. Be sure to try some salmorejo, the Andalucian version of gazpacho. Peek into every patio and entryway to see the colorful tiles (azulejos).
I've been to Sevilla and Cordoba 3 times, Ronda twice, and I know I'll be back. I hope to return to the Alhambra a second time.