Honestly, I can't recommend the GBASP enough. It's small, it has a lot of power for a handheld of that era (enough to pull off texture-mapped polygonal graphics at an acceptable frame rate) and the addressable ROM size is practically limitless, going all the way to 64 MB.