I'm going to back way up here and say start with just 1 new knife: the gyuto.
If you're starting relatively flesh and you're cooking for a growing family, then get something 240mm long.
To see what 1 good knife, some focus/ practice on technique, and of course dubstep will get you, just watch some of our own Theory's(pcckitchen) videos:
https://www.youtube.com/watch?v=vPiz6Aaa7Eg&feature=youtube_gdata_player
[video=youtube;vPiz6Aaa7Eg]https://www.youtube.com/watch?v=vPiz6Aaa7Eg&feature=youtube_gdata_player[/video]
Practice is a big part of it, but its as much about thinking and planning your work/cuts as anything.
Once you get used to it, the extra length will come in handy and will make it work well as a slicer. If you master your gyuto skills, you might not ever NEED a petty, paring, or slicer. And honestly for as little as a paring knife would get used in Paelo cooking (not much fruit), you can probably get by with what you have just fine. You money will get better value in a gyuto that you really love, a couple decent stones, and a nice big cutting board.
There are good stainless steels out there, but if you can discipline yourself to give it a little extra care (dont put it away wet), carbon steel will give you a better cost/performance ratio, will make learning to sharpen easier and, IMO fits with the whole paleo mentality and also your desire to look like a bada$$.
One feature that will help with comfort is a rounded spine and choil, with a couple clamps, sand paper, and elbow grease, you can do it yourself, but some knives come with the extra finishing work already done.
Anything that you get from Japaneseknifeimports.com, or korin will be excellent quality. Spend some time looking at pictures and then give them a call.
Lastly, as others have mentioned, the best way to get peak performance out of your new toy is to learn how to keep it sharp / make it sharp yourself. The factory edge will last for awhile, so use that time to learn /practice sharpening on the old Costcos.