First of all, I think it would be beneficial to lose the concept of "mic ins". I see a lot of people come here looking for "mic inputs", maybe because they're used to looking at mixers and the like.
A mic input is really an input to a microphone preamp. You can't get past the requirement of a microphone preamp. Not only does the mic pre amplify your mic signal to line level, it colors the sound while doing so...sometimes good, sometimes bad. That's why there are 5000 different mic preamps out there ranging from $50 per channel to $2000 per channel.
Personally I don't recommend getting a soundcard with built-in mic preamps. If the preamps it comes with suck, then you just wasted your money on them. Often times there will be a way to bypass the oncard preamps, but you still paid extra for them (or quality was sacrificed elsewhere). That's why there really aren't many soundcard systems with mic preamps....the Aardvard Q10 I believe has pres, and so does the Delta 1010lt.
The best route to take is to get a typical soundcard with line level inputs, and then use external preamps. This gives you much more flexibility for your dollar. After all, you wouldn't by a soundcard that had microphones pre-wired to it!

(ok, bad example)
You can either get standalone microphone preamps, or you can use the mic preamps in a mixer. Every mixer that has mic "inputs" has mic preamps. The catch with a mixer though, is that you may only be limited to 2 channels even if it has more than two mic preamps. You'll want to look for a mixer that has channel inserts or direct outputs for each channel such that you can isolate each individual preamp. Really though, if you don't need a mixer for anything else, buying standalone preamps isn't a bad idea.
For an absolute beginner 4 channel package, I would recommend getting
a m-Audio Delta 44 which has 4 inputs and 4 outputs via 1/4" balanced jacks in a breakout box, and then getting a couple m-Audio Audio Buddies, which are by and far the cheapest usable preamps on the market. The Delta44 runs about $230 and the Audio Buddy I think runs at $79 for two channels. So your total cost would be $230 + $79x2 = $388. Instead of the audio buddies, you could also look for a used Mackie 1202 VLZ mixer which has four mic pres and channel inserts so you can isolate them. They go around $200.
That's about as cheap a way as I can think of to get into four usable channels.
Slackmaster 2000