I've done the trip along the southern border in October so what I looked for in a park may differ from what you will want in May. AC/hookups weren't important to me in the
fall. I also like to limit the amount of time on interstate highways.
There is an RV park in Whites City that has hookups. It is near restaurants, laundromats and the park entrance. I was not impressed and did not stay there. five miles west is a blm camp called sunset reef. rv sites have a covered concrete pad, fire ring and grill. no water or hookups. the outhouse was very clean and there is a dumpster. If sites are full there is enough space to park anywhere on the perimeter. It is fcfs and free. Water is available at picnic area at rattlesnake spring about a mile away. Carlsbad Caverns are incredible. If you are able to get on the Kings Palace tour it is well worth it. If not, the self-guided tour is great. We managed to do both. Hopefully the bats will be back in May as it is fun watching them fly out at night.
Guadalupe rv camp feels like an overnight at walmart except the scenery is much better. It is a paved parking lot with lines to delineate campsites. there is limited water available in the bathrooms. A lot of nice hiking trails start from the campground. It is only about 30 miles from sunset reef. If I were to do it again, I would stay there and explore Guadalupe.
Following 9 across the southern border you will come to Columbus NM. Pancho Villa SP is one of my favorites. It is on the site of camp furlong. It has hookups, showers and a nice museum about Pancho Villas raid. New Mexico parks are a bargain. Only $14 for utilities and the park is very clean and well maintained. The town also has a nice museum across the street. Not much in town to see. They have a nice library (which loans DVDs) and an old hotel with an art gallery. It is 3 miles from here to the border. You can park at the border and walk into Palomas to have lunch at the pink store and explore shops in town.
Chiricahua is one of my favorite parks. It is a small campground with no hookups but some of the best hiking trails IMHO. The campground will test your backing skills. It is worth a visit. Nearby is Fort Bowie which is interesting for history buffs.
Kartchner caves has hookups and showers. The cave tour is really nice. This park is very popular so book well in advance if you can. Nearby is Fort Huachuca. It is an active military base and has several interesting museums and one about the buffalo soldiers that were stationed there.
Organ Pipe Cactus National monument between Yuma and Nogales is another nice campground. No hookups but they have water, showers and a dump site. Stock up before you get there as there are no places to resupply. There are some nice hikes in the area and the varieties of cacti are impressive.
I'm sure I've missed a lot of nice places, so I am always willing to return there.
Wayne