Starting with Gameboy might be a bit daunting but if you're reasonably comfortable with C then I don't think it's too bad. If you're not too familiar with the hardware side of it then that might be a challenge, but the advantage with the Gameboy is that there's tons of documentation and tutorials out there which can probably help you work though the details. Really the big thing is to just be ready to do lots of reading XD You need to get a base-level of understanding of the system before you start coding. git says it took me around a year to get it functional and playing most ROMs, but that was with some big breaks in-between.
Also, that's a very good question. For performance, it was never an issue. I started it with a focus on keeping the code clean vs. worry about performance and it turned out fine, I've run it on a cheap 1.6GHz machine and it didn't even reach 25% CPU usage, so IMO I wouldn't worry about it. This also doesn't vary that much ROM to ROM.
For the ROMs I tested, for the most part every ROM tended to uncover something new, but the Gameboy has a pretty nice progression of "easy" to "hard" ROMs if you just sort by the MBC type, and also the BIOS is a pretty good test of basic functionality. Additionally there are a few different test suite ROMs out there that are fantastic, they'll run through every instruction or piece of functionality and check for the correct results, they saved me tons of time.