About 35 miles north of Bernallio is Cochiti lake. There are websites for the lake and pueblo. The spillway out of the lake is on The Cochiti Pueblo reservation. It used to be good fishing but you have to pay to fish there. Don't know about fly shops.
If you have time for some really good food try this place in the North Valley. http://www.elpinto.com/location#.U4j6Q8JOVLM
El Pinto (North Valley)
10500 4th Street
Albuquerque, NM 87114
Because for me it's all about the food. Jim
I'm either going to, coming from or thinking about fishing. Jim