Castlevania IV has the better graphics and sound, that's no contest. Some people aren't a fan of the larger player sprite (some people have the same complaint for Mega Man 7). I've also heard the complaint that the game is now too easy because Simon can whip in any direction and change direction in mid jump.
One thing I really like about IV over 3 is the dedicated button for your sub weapon. In 3, you have to hold up and press attack to use your sub weapon. This makes it annoying to use your sub weapon on or around stairs. It can be hard to use your sub weapon, in the direction you want to face, while on stairs. And if you're next to stairs you may accidentally start walking up them instead of using the sub weapon, which will usually result in your taking a hit.
But here's the main two arguments you see: Multiple playable characters and branching paths.
CV3 has 4 playable characters. Trevor, Grant, Sypha and Alucard. CV4 only has 1, Simon. One could argue that Simon's new abilities makes it a little different than just a loan NES Belmont. But the additional characters in CV3 definitely make that gameplay a lot more diverse. Alucard can turn into a bat and fly. Grant and climb on walls and ceilings. Sypha's sub weapons are powerful magic spells. But one of the main arguments for Super Mario 3 versus World is that 3 had a ton of power ups and World only had a couple. I think the same argument can apply to World and 4, sometimes less is more. In World, they refined the flying ability to make it much more powerful, and Yoshi is the single most amazing power up ever. In CV4, Simon is a lot more powerful. He can whip in any direction, jump onto stairs, and use his whip to swing adding a whole new layer to the platforming. CV4 may only have a quarter of the amount of playable characters that CV3 had, but they focused on adding more depth to that single playable character.
Then there's branching paths. Here's an honest question... Are branching paths actually better than a linear path? Branching paths did add a lot of replay value to CV3, especially since different paths lead to different playable characters. I had a lot of fun replaying CV3 to try and find all the possible paths. But I don't think I had any more fun than I did playing through CV4 for the first time.
These days, I kind of prefer the single linear path. I've played both games many times, and I'd prefer to be able to play through all of the levels in a single go. If you want to play every level in CV3, you have to play through it at least 3 times (or 4?). This is nice if it's your first time with the game, but it's more of a chore for me at this point. And I know I'm not the only person to feel that way.
Castlevania 3 - Linear Version: http://www.romhacking.net/hacks/4735/
This above linked hack makes it so that you can play every level in CV3 with a single play through. If it's your first time playing the game, I highly recommend playing the vanilla game with the branching paths. But this hack is really nice for people that have beaten the game many times over. I've grown to appreciate the linear path of CV4. Maybe it's the "more time to play video games as a kid than as an adult" thing. But I just recently played through CV3 using the above linear hack and had a blast. I would have done a different level order, but it was a pleasure being able to play every level in the game in a single go. And it made me realize there's a couple of levels that I almost never play.
I always thought CV3 and CV4 had about the same amount of levels. A quick Google says that CV3 has 15 and CV4 has 11 levels. So CV3 has 4 more levels, but again, you can't ever play them all in a single go. You'd have to start form the beginning 3 or 4 times.
CV3 might have a few more levels, but I'm not sure how they're being counted. There's a lot of repeated content in CV3. Did they count the clock tower twice? I kind of view that as one level. Did they count both parts of the forest? I count that as one level as well. CV3 also reuses a couple of bosses. You realize this a lot more when you play the linear version. You fight the cyclops 3 times, the mummies 2 or 3 times, and the gargoyle twice. The next time I play through CV3, I'll have to count the levels myself.
One other common reason you hear that CV4 was a step back from CV3 is the fight against Dracula. The below spoiler tag contains spoilers for CV3 and CV4!
I'm voting that both are equally as great. There are things that I love about both games. And with the controls and sprite size, they both feel like two totally different games to me.
....but wait; III had a famicom version with superior soundtrack!... anyway, the third time is a charm. 