I'm looking at a cheap board to start on and I'm wondering if I'll be able to fit a Picoblaze, LEON, S1, or OpenRISC core on there. Is there any way to tell?
Yes, you can synthesize IP cores without actually needing the hardware. In your synthesis tool you get to pick which FPGA chip you are targeting, and when you synthesize it will tell you what % of the FPGA's resources it used to fit it on there, or if it could not fit it.
In fact, it's a good idea to use the synthesis tool and run everything in simulation before you plunk down money on a board. It's not like AVR where you can get a whole setup for $20, the range for decent starter FPGA boards is $100 - $200 depending on the number of features and helper chips you need.