First, take the South American Handbook rather than the LPlanet I reckon. In strict acclimatisation terms, it's better to go Quito then La Paz, you'll have a stinking headache for a few days if you land at 4100 metres from sea level, but people do it all the time. The city itself is between about 3600 metres and 3900 metres and it doesn't help that most of it is on the sides of a bowl so you have to walk up it... Incidentally, they've had hidous floods there recently.
I guess it depends on how you view discomfort. When you do arrive, take it very, very easy. Drink lots of water. Don't rush around. Don't hit the alcohol and you should be okay within four or five days, though not properly acclimatised.
May is a bit early for trekking or climbing in Bolivia I think, but it all depends on what you're planning to do and where. The dry season usually starts in June, but then the weather's so variable these days that it's hard to know. I guess you're thinking of travelling overland through Peru and finishing in Ecuador, which makes sense, though there's nothing particularly wrong with doing it the other way round either.
Quito's at about 2600 metres, so much less of a shock when you arrive. In a way it make sense to go to Ecuador first. The trekking isn't anything like as impressive as in Peru or Bolivia, partly because the mountains tend to be isolated volcanoes surrounded by paramo, sort of high altitude scrub. It is good for climbing easy, non-technical snow peaks though, something like Cotopaxi with a guide is very, very feasible and beautiful too. Safari in Quito - www.safari.com.ec - is a good starting point for a reliable, professional guide.
From there you could travel down by bus through Peru, check out the Cordillera Blanca and the Huayhuash before heading on south to Cuzco. You have to do the Inca Trail, though it's a bit of a cliche, it's amazing. The Ausangate Circuit' is wilder, higher and quieter, but an amazing walk around a really beautiful mountain area.
From there, Bolivia. I can recommend the Illampu Circuit out of Yossi Brain's Bolivian trekking guide, but there's loads more to do there. You can't really go wrong. One of the advantages of doing it this way round is that it'll be a little warmer at altitude in Bolivia when you get there. Early in the winter it can be really cold.
Other stuff? The South American Explorers Club - www.samexplo.org - is a good information resource and has club houses in Lima, Quito and Cuzco, but not in Bolivia, though it has information on the area - whether it's worth it is a tough one to call, depends how much you're going to use it. Not sure what membership is these days. The club houses are good places to chill.
At any rate, I'm thinking of heading out to Peru in July if I can - Swis where are you? - so I might even see you down there. Oh, learn some Spanish before you go. It will make your life massively easier.
