You could buy some of the newest boosters if you want to collect any type of card and not just the rare ones. When I first got into the TCG during the Ruby and Sapphire days, I only bought the newest sets and occasionally bought some older cards that stood out to me on eBay. Tins are also a good thing to get started with because you're guaranteed a fancy holographic card and four boosters.
I really like Meowth, Cubone, Growleth, Nidoking, and Hounder
The four HeartGold Soul Silver sets (HeartGold SoulSilver, HS Unleashed, HS Undaunted, and HS Triumphant) should have your favorites in them. Otherwise, turn to lots that are on eBay that sell commons from the early sets, as 4 of those 5 are commons in the early sets (Growlithe is one in the Base Set, Meowth & Cubone are commons in the Jungle set, and Houndour is a common in the Neo Discovery set, iirc). For most of the older Nidoking cards, you'll probably want to buy them as singles off of eBay.
Well, you're going to have to shop for singles, then. eBay, Amazon, and TrollandToad are the best places to find singles. There are also quite a number of other online shops for singles that are good, their names just escape me at the moment.
If you want to collect i think psa is the right way to go
PSA graded shopping might be out of the budget range of most people just getting back into it or just starting collecting. Also, for most of the cards featuring doglover44's favorite Pokemon, they aren't going to be worth having PSA graded. I think the only ones worth being graded are the 1st Edition Base Set Nidoking, the 1st Edition Gym Challenge Giovanni's Nidoking, and the Aquaopolis Crystal Nidoking. None of the others and none of the rest of Nidoking's are worth having graded, and that's primarily because of the relative rarity of those three cards. None of the other 4 Pokemon have anything anywhere close to that rare or valuable, and none of the other Nidoking cards even approach these 3 in value.