If you want to minimize county splits and make the map look good, here you go:
Only two counties are split, Valencia and Curry. NM-01 is 60-39 Obama and 46/43 Hispanic/white, NM-02 is 52-46 McCain and 51/43 Hispanic/white, and NM-03 is 63-36 Obama and 39/38/20 Hispanic/white/Native. The districts' population deviations are -14, -47, and 61, respectively.
Here's another alternative; this time, NM-01 goes up into Sandoval County. The two split counties are Roosevelt and Sandoval.
Doesn't really change the numbers significantly; NM-02 goes to 51-47 McCain. The deviations are 28, -150, and 122.
What is the population of the purple area of Roosevelt County in the second map. Could you get that same population in Torrance or Catron, and avoid the town split of Portales?
How much over would the green district be if it included all of Roosevelt County?
In Arkansas 2000, the four districts were +0.00%, -0.34%, +0.66%, and -0.32% from the ideal population, with a 1.002% difference between the smallest and largest districts. The redistricting law also had versions in case someone challenged the whole county version on "one man, one vote" grounds. They in effect challenged someone to sue, and piss off a few county clerks and a few 1000 voters. And it may have shown a good faith effort to achieve population equality.
In New Mexico, I assume if any of the neighboring counties, including Cibola or Torrance, it would put the central distict over by more than 1%. But what if you included all of Roosevelt in the green district, and then equalized the population of the other two districts with the split in Sandoval. So the green district would would have +X over the ideal population, and the other two would be -X/2 (for the purpose of this exercise, assume that you can split a VTD to get to precisely equal districts. Is (X + X/2)/Ideal less than 1%?