Here are the basic choices:
ARM SoC Based
ColdFire SoC Based
68K Family (68000 or 68020/EC020)
8-Bit CPU (Z80 or 6502)
Interested, but no idea which to choose
I think it would make sense to use the ARM SoC. That should be the cheapest part.
I would prefer a lot of integrated toys (timers, DRAM controllers, ethernet, etc) so that one could get it up and running quickly. A Serial interface is vital for getting the thing running without having to worry about gfx and TCP/IP stacks :-) These SoC's tend to provide a normal Address/Data bus as well, so it would be easy enough to add a VGA controler and other fun stuff as well.