I think your location depends on what you most want to see. In and around the wetlands in the east and central Algarve many of the species seen are birds that a relatively straightforward to see in the UK plus the following regulars in April/May (some need extra effort)
Red-crested Pochard
Greater Flamingo
Little Bittern (not Tavira)
Purple Heron (not Tavira)
BW Stilt
Kentish Plover
Collared Pratincole
Purple Swamp Hen (not Tavira)
Audouin's and Slender-billed Gulls (best around Tavira)
Hoopoe
Bee-eater
Crested Lark
Short-toed Lark
Zitting Cisticola
Sardinian Warbler
Great Reed Warbler
Woodchat Shrike
Azure-winged Magpie
and Golden Oriole a little inland
Spectacled Warbler and Lesser Short-toed Lark are to be found at Castro Marim at the extreme east Algarve in the right habitat.
In the far west - inland habitats are closer to the coast although there are few wetlands - f you stayed in Lagos or nearby you could commute on a local bus easily to Sagres and walk around the peninsula. You could even try and be based in Sagres but that may be difficult for a package holiday - though possible at Martinhal - just by Sagres.
Species difficult or impossible in the UK in the western Algarve in April/May are:
Little Bittern
Short-toed and Bonelli's Eagles
Little Bustard
BW Stilt
Kentish Plover
Hoopoe
Bee-eater
Crested Lark
Thekla Lark
Short-toed Lark
Tawny Pipit
Black-eared Wheatear
Blue Rock Thrush
Spectacled, Subalpine, Dartford, Great Reed and Melodious Warblers, Iberian Chiffchaff
Iberian Grey Shrike
Woodchat Shrike
Red-billed Chough (only place in S.Portugal)
Azure-winged Magpie
Golden Oriole
Rock Bunting
Others like Woodlark, Nightingale and Cirl Bunting are common birds in the right habitats. Others like Lesser Spotted Woodpecker and Hawfinch are easier than in the UK.
I personally don't bother too much with Monchique - all its species are found in other areas to the southwest and a fair few more. It is visited a lot by visitors because its the highest point although just 900m and not high enough to change the birdlife much - its habitats are quite fragmented and better areas are to be found at lower elevations.
If you were to move around 80kms inland, just north of the central east Algarve, (although an impossible package base and very difficult without a vehicle) a whole lot of other species are normal in the right areas of the Baixo Alentejo - some
additions to the Algarve's birds in April/May would be:
Griffon and Black Vultures
Spanish Imperial and Golden Eagles
Black-winged Kite
Black Kite
Montagu's Harrier
Lesser Kestrel
Great Bustard
Black-bellied Sandgrouse
Eagle Owl
Great Spotted Cuckoo
Roller
Calandra Lark
Rufous-tailed Scrub Robin
Rock Sparrow
Spanish Sparrow
...meant to mention Red-necked Nightjar, which is present across the Algarve, especially a little inland. Also, early May is also when the scarce White-rumped Swift returns - worth checking around inland bridges in hilly areas anywhere in the central and east Algarve - the most western pair recorded I found last year near Loulé/Faro.
Also I should mention that many of the more inland species I mention for the western Algarve are also in the far inland east - though a bit less practical on foot, bike or public transport.
My website describes the the birdlife in the different areas throughout southern Portugal - maybe of interest:
http://algarvebirdman.com/
Cheers
Simon