Generally speaking, an anvil of 125lbs is what I would recommend. You can certainly work on smaller ones, but the smaller ones tend to make you work harder to achieve the same thing.
The going rate is in the $3-$4 per pound range for an anvil that is in excellent shape. Of course try to get the best price you can. When checking an anvil, don't pay too much attention to how it rings or doesn't. The best way I've found is to carry a small (3/8" or so) ball bearing around with you. To test an anvil, drop the bearing onto the face from about 1' above the surface. A GOOD anvil will bounce the bearing back to your hand, and maybe a bit further. If the bearing bounces very little, let that anvil pass. It's very likely that it has been in a fire or something else has occured that has softened up the face.
My personal favorite brand is a Trenton, but Peter-Wright, Mouse Hole, Fisher, and several others are excellent brands to look for also.
Anvils keep getting tougher to find....not because everyone is using them, but because more often than not, museums and other historical outfits are buying them up for displays. You might check out some of the new anvils. I can't remember the name right now, but there is a gentleman in Washington state who is casting anvils, and all reports I have heard say they are excellent. You migh also look into
http://www.anvils.nimbaforge.com
http://www.oldworldavils.com
