I have an idea to make a game like Faceball 2000, which was a first-person-shooter on the Game Boy. Obviously, I'll keep in mind all of the limitations, like the controls being up/down to move forward/backwards, left/right to turn and B to shoot. There'll be no shading to match how Faceball 2000 looks and a shader to quantize colors to just 4. If this is allowed, what'd be allowed in terms of frame rate? Faceball 2000 ran at around 5 FPS, which I know many people cannot tolerate, but would 20 FPS be ok? 30? 60? Uncapped?

As long as you use the resolution, input and colour limitations, you can do basically whatever you want, including 3D games.