Like I said, the original 8 bit series + the 7 and 8 that were on SNES and PS1. PLUS try 9 and 10, they were great too (released on Wiiware, PSN, Live).
And I KNOW you probably have not tried the GB versions. They are the most underplayed Mega Man games. Give them a shot.
Also, if you just are tired of the Blue Bomber, try the Homebrew NES games "Battle Kid and the Fortress of Peril" and "I Wanna Be the Guy".