Melty Blood Type Lumina is my favorite fighting game.
The movement is crisp, Raito never misses with the music and the spritework is some of the best I've seen in 2D fighting games. Gameplay wise, the game centers around the concept of "aerial footsies". The neutral presented is somewhat scrambly but once you understand how it works, the game becomes a lot more fun.
New players hopefully won't have much trouble with execution as it's quite lenient, and there are autocombos to help out, although you can turn them off if you feel you no longer need it or find them intrusive. At the same time, the Reverse Beat mechanic lets you chain together normals in whatever order you want giving you a level of freedom not found in many other games. Characters are easy to learn on the surface, but once you start interacting with the game's strong defensive mechanics using your character's tools, things get more interesting.
If you want to know more about the cast of Tsukihime, you can get more mileage out of character interactions by playing through the various single player modes. However, you'll get the most out of these characters by reading the source material, although it's not necessary by any means to enjoy this game.

This is all without mentioning the rare practice of DLC being free across the entire lifespan of the game. Awesome stuff on display here.