There is actually not a whole lot apart. (In looks.)
Nidoqueen is a great wall to tank hit out ingame. And when I first played through Fire Red, Nidoqueen was one of my team members. It comes extremely useful against the Elite 4 and with the movepool of learning a move of almost every type, it has great coverage ingame.
Nidoking is offence. He is a great sweeper ingame and as a fact learns a move of every type. His Special Attack is great, not to mention his Attack, so he can become a great Mixed Sweeper. Nidoking is an awesome way to sweep the game up.
By the way, over the stats, they both have 495 base total, meaning there is not much to compare between the stats. Nidoking has better offence, while Nidoqueen has better defence. They have different roles to play.