Something like an STM32 Discovery board is a good option for recapturing the mid-90s magic. You can get a ~200-MHz Cortex-M4 or M7 with a few MB of flash, external SDRAM, and a display for less than $100. They have really basic hardware 2D accelerators.
The on-chip peripherals are well-documented, but off-chip peripherals require some digging to figure out how to program correctly.
You can debug with GDB surprisingly easily, or find a Forth to throw on there and just start poking registers.
No. Microcontrollers are the improper solution for this problem.
You can run full blown Linux efficiently at 500MHz or 600MHz processors like STM32MP1 processors, powered by AA batteries or other small battery packs.
There's also SAMA5D2, and a few other competitors in this space (both above, and below, the STM32MP1).
When we're talking about "consoles", that's "plug-and-play executables", meaning you now want a proper compile / library -> ELF + loader == Linux kernel, security, etc. etc.
Besides, a DDR2 chip gets you like 512MB of RAM for $4 and easily fits within the power-constraints of AA-batteries. There's very little benefit to going to the microwatt-scale devices like STM32 Discovery.
----------
Microprocessors for the win. Entry-level MPUs exist for a reason, and there's a ton of them well below Rasp. Pi in terms of power / performance.
There's many at the 2D level of graphical performance, but 500MHz is still a bit low for this. You'll probably want to reach into faster 1000MHz / 1GHz MPUs and push into STM32MP2 if you're reaching into 3d levels of performance. (Which is beginning to look like a cut-down cellphone chip really)
I guess it depends on which part you think is fun. Using a big microcontroller is more about pushing the hardware to its limits. Using a small Linux system is about taking advantage of existing libraries. The Playdate has an STM32F7 and it seems to do pretty well as a console.
I liked the 32F746GDISCOVERY which is $56 at Digikey. It has a Cortex-M7 CPU, 1 MB built-in flash, 8 MB of SDRAM, and a 480x272-pixel touchscreen. Games can go on a microSD card. There's a USB OTG port you can use for input.
A low-res screen like this works well because the chip can't rescale its video output.
ST provides libraries for all the peripherals so it's pretty easy to jump in if you know C. I think microPython works on a lot of these boards, too.
The on-chip peripherals are well-documented, but off-chip peripherals require some digging to figure out how to program correctly.
You can debug with GDB surprisingly easily, or find a Forth to throw on there and just start poking registers.