I crossed in late July / early August 2017 and stayed mostly on larger roads so can't help you with offroad aspects as much.

However, a few thoughts:
* It is an arid region with a large day/night swing. So even though I was prepared for -10C overnight (14F), it also warmed up to +10C during the day (50F). May should be warmer than i went, so I'd think of having a warm enough sleeping bag and sleeping a little if slightly cold.
* While not completely flat (other than salt flats which are flat); there wasn't much in way of climbs once at elevation. The general area was between 3800m and 4200m, so one does want to take cautions with acclimatizing.
* Some of the smallest settlements didn't have a huge amount in way of stores/shops. Enough that I could typically get things to eat, but don't expect a lot of variety.
* I suspect May is probably fine, but I wouldn't go a few months earlier as the Salt flats flood during the wet period and then dry up.
* In just the past few years they finished paving the main roads to Uyuni. There were big construction projects underway from there south to Argentinian border as well. If you look at trip reports for that area - pay attention to the dates if it describes the road as being extremely rough
* If you are a US citizen, Bolivia has some extra provisions and costs to get a visa at land border. Look up details prior to the trip.

As far as places go along my route:
- Puno, Copacabana, Uyuni were what I'd describe as "backpacker towns". Lots of tourists, laundry service by the kilo, tours, etc.
- El Alto was a large city complex (I didn't go into La Paz)
- Oruro was a mid-sized town with lots of services. Juli Peru also had reasonable services.
- Outside of those sorts of places, the small hamlets are small hamlets.