I didn't grow up playing a lot of Castlevania games (only played one obscure cell phone port), but being able to fight as Link in Dracula's Castle (with probably the best video game tracks in a Smash game) and fighting Dracula as a boss not only makes me want to start playing Castlevania games, but makes me wish for a Legend of Zelda X Castlevania crossover. Man, where am I even gonna start with the Castlevania games, though...
For DLC characters, throw in Sora from Kingdom Hearts so that we not only get another Square Enix rep, but more music as well. Cloud only brought two tracks from Final Fantasy with him, so hopefully we get more music from Square this time around.
I've personally always wanted to see a Metroid X Castlevania crossover, complete with a Death/Ridley amalgamation and holy beam/suit for Samus. Thinking about it now though, Link using the Alucard Shield (and/or the Shield Rod) would be pretty sick.
As for where to start, I guess it depends on if you want to start with the classics or play the later metroidvania ones. They're both really good in their own right and you should play both. Can't go wrong with the first one, III, and Rondo of Blood are considered the better ones (there's an SNES remake of Rondo called Dracula X, don't bother with it). For Super Castlevania IV you'll hear different things depending on who you ask, since some find the whip mechanics to make the game too easy, but even then the classics are still more of a challenge than the later games.
The first of the metroidvanias (unless you want to count Simon's Quest, I don't really) is Symphony of the Night, and it's probably best to start there. It's the only metroidvania to be released on a console, so it has a bit more detail, as well as one of the larger castle maps. The metroidvania games can get pretty broken if you know what you're doing, and this game is the most notorious for it. So in that regard you should play it before the GBA/DS games, otherwise it'll be a cakewalk by the time you get to it. The Sorrow games are really great, and Portrait of Ruin gives you a lot of modes for replay value. Order of Ecclesia is also fantastic, since it brings some much needed difficulty to the metroidvania titles. I wouldn't bother with the 3D games, since they're mostly of middling quality.
If you have a PSP you can get Dracula X Chronicles, which is a remake of Rondo of Blood (along with having the original too). SotN is also unlockable, so you get the best of both worlds.
Sorry if this is too off-topic btw, I just noticed throughout the thread a lot of people were unfamiliar with the series. I was finding it baffling that people didn't think Simon was going to be in the game, and then I realized there hadn't been a notable game (asides from the Lord of Shadows games) since OoE, which came out 10 years ago.