If you can't trade to evolve, that is something to take into consideration. For a psychic type, I would highly recommend trying out Espeon (daytime evolution of Eevee, as Ludger mentioned). One thing to be aware of about other evolutions that require evolution stones is that I think the trainers only call you to give you stones in Crystal. In Gold, I think your only option for getting the stones is a lot later in the game, and you only get one of each, so definitely not practical. (You can also get evolution stones from Mystery Gift, but you need a physical cartridge and GBC + another GBC and GSC game or cartridge + N64 + transfer pak + Pokemon Stadium 2 to do that, and the odds are still low. Given that you can't trade, I'm guessing you're not using a setup that would allow you to do mystery gift.)
Ampharos (final stage of Mareep) is a really interesting Electric type in that it doesn't fit the normal electric mold a la Pikachu/Raichu. It isn't that fast, but its defenses aren't bad, and it has a pretty good special attack (if you haven't played since RBY, you should be aware that the special stat split, so some Pokemon have slightly different uses now).
I don't think Vulpix can be found in Gold (Growlithe is the one that's available instead). It'll be a long time before you can evolve a Fire Stone-evolving fire type, most likely, so that's something to be aware of when making your solution. There aren't a ton of great fire types that are jumping to mind for me off-hand (Ponyta/Rapidash can be found at some point, there's Slugma/Magcargo (fairly weak, though), Houndour/Houndoom (part dark, not available till fairly late in the game), and maybe a few others.
Normal types: You can always get a Snorlax again, though you'll have to wait till post-Elite Four, and there's only one available. For a Gold-exclusive, you could look at Ursaring. I don't know if it's as tanky as you're looking for (90/75/75 base stats for HP/Defense/Special Defense), but it's not bad. I can't remember when you can first pick up a Teddiursa, though. Or you could use Miltank, who is pretty tanky (95/105/70 HP/Defense/Special Defense).
For fighting types, you could use any of the Hitmons (Hitmonlee, Hitmonchan, or the new Hitmontop), Heracross (part bug type), Mankey/Primeape, Machop/Machoke (trade evolution, though), etc. For ground types, Nidoking/Nidoqueen is always a solid option, and you can get a Nidoran on route 35/36, so fairly early. If you wanted to try out new Pokemon, I'd recommend Donphan, but that's Silver-exclusive, so you need to be able to trade to get one.
You can't get it for a while, so it isn't that practical for the main game, and it takes a long time to train, but Larvitar/Pupitar/Tyranitar is fun to try out. It's sort of the gen II equivalent of Dragonite. It's Rock/Dark, so it doesn't really meet what you said you wanted type-wise, but it's interesting.
One other mechanical thing to be aware of is that the attack DV (I don't know if you ever played competitively in RBY, but if you didn't, think of DVs as genes dictating a Pokemon's potential in each stat) determines gender. For Pokemon that can be either gender (not all male, all female, or genderless), the higher attack DVs are for males and the lower attack DVs are for females. The exact split depends on the gender ratio (e.g., for starters, 1/8 of starters are female, so all female starters have attack DVs in the bottom 1/8 of the scale, i.e., they have really bad attack stats relative to their max). If you're training something that needs a decent attack stat/uses physical attacks, you may be better off picking up male Pokemon in Gold as a result. (This does not apply to newer games, if you decide to play those after playing Gold.)
So I would try Feraligatr/Ampharos/Espeon/Normal type/Fire type/Ground or Fighting type.
