The 26" size can mean any of five different rim sizes. I am assuming that these are 559 mm or mountain bike rims. Most tires will be stamped with the bead seat diameter. If you want fenders, a 700c wheel wouldn't work very well as the rim would have a 63mm greater diameter, thus you would have less room. You would also have to move the brake pads up 31.5mm.
Another possibility is 650b.
If you want to stick with 26"tires Compass has some that are supposed to be pretty good.
www.bicyclequarterly.com
27" and 700c wheels would not be a good solution on a small frame like this.