I live in New Mexico, and have done lots of hiking all over the state.
Several things first. (1) In the northern part of New Mexico (anything north or, say, Socorro, the Forest Service campgrounds will be closed November 1st until April 1st. (2) If not closed, you will generally have to supply your own water.
OK - options for you.
First, instead of the Sandias, I might suggest the Manzanos, the range to the south. Get off at the Tijeras exit of I40, go south, and there are a series of Forest Service campgrounds along the east side of the Manzanos. The first is Fourth of July campground, with some nice hikes right there. Further south is Red Canyon campground, with a nice loop including a side trail to Manzano Peak (over 10000 feet).
Besides @OlinLathrop's suggestion of Mt Taylor (great views, lots of snow right now), there are a variety of campgrounds on the south side of I40 along the Zuni mountains. I've done less out that way, but there is plenty of hiking there as well.
Somewhat off the beaten path, but El Morro National Monument is less than an hour south of Grants NM. They have a campground (although it does not seem to be mentioned on their web site anymore - you should call first) and some day hikes there. Along the road are various turn offs in to the El Malpais (mostly BLM land), with hikes and caving in the lava tubes (great fun).
But, for the true New Mexico experience, I would direct you to Chaco Canyon. It will be about 2.5 hours from Albuquerque, with the last 30 minutes on a pretty good dirt road. The camp ground is open year round, and water is available. There are 4 back country trails in addition to the great house ruins in the canyon. The loop (3-4 miles) up the north side of the canyon to the Pueblo Alto complex has fabulous views of ruins in the canyon, as well as to the north into Colorado. The longer (7 miles) hike to Penasco Blanco at the end of Chaco Wash takes you by many petroglyphs. Both can be done in one day, if starting early. And, providing you have talked to the rangers before hand about the road conditions, you can exit the park to the south, meeting up with I40 near Gallup (the north entrance dirt road is pretty good, the south may require real four wheel drive).
My two cents.