Hi Steve,
Couple of areas i'd look at, Pindos or Epirus.
I'd say Pindos is a little more wild than Epirus but both areas are beautiful with enough wilderness to get lost.
The weather around that time period is pretty unpredictable here, i've had Easters where i've been walking around in shorts. and tee-shirt sweating my bollox off and other Easters where i've been in 2 jumpers and coat and was still cold.
The weird thing about the climate here (as opposed to England where i'm from) is that if your active you really only need a thin layer of clothing.
It will get cold at night in those areas though and i'd expect at least 1 day of rain out of say 10
If you start heading up higher than say 1000m then i'd expect snow to still be on the ground at that time of year.
If it's height your after you have Mt.Timfi is just under 2500m, Mount Smolikas is just over 2600m, both in the Pindus range.
If it's forest areas then there are miles and miles of forest, with many gorgeous little villages to stop off and refuel.
If you pick your spot well water shouldn't be a problem at that time of the year as the snow is melting on the peaks and we still get several days rain a month around that time.
As always though make sure it's well filtered, boiled or treated.
On the whole Greeks in these areas are extremely friendly, as you get closer to the border they tend to be a bit wary of foreign looking people as there has been many problems with drug and people smuggling from the various borders, Albania in particular was a major problem 10 to 15 years ago.
Once you've broken the ice though expect to be greeted warmly.
Decent scale and detailed hiking maps are a major problem over here.
I usually take a GPS with
http://www.openstreetmap.org/ maps, a computer print out plus my phone with backup batteries.
As long as your not walking over peoples crops or through their back gardens access is pretty much open to anywhere you want to walk.
Only thing that really really pisses locals off is folks starting fires.
Personally when i'm camping in Greece i only use a stove rather than starting a fire to cook from.
It shouldn't be tinder dry that time of year, but still it's frowned upon to have open fires in national parks at any time of the year.
Hope that helps
Cheers
Mark