It's called depth, and it's the mark of a good game. If you can jump into a game with practically no knowledge or experience (real experience, not arbitrary variables in the game determined by how long you've played) and are immediately the best at it, then it's probably a very shallow game (i.e.: most CoDs, DoA, etc).
A good game will be easy to get into, hard to master. Mortal Kombat is a good fighting game for beginners. It's deep enough that it's more than button mashing, but not too deep that it won't scare off people who are insecure about it. MvC is another good example. If you want to get better at it you just gotta learn... Like everything else in life. Practice, practice, practice. Like anything else that involves any level of skill, the more you learn and practice the better you become.
Personally I'm a much bigger fan of SF and BB. BB is quite complex from the get go so it tends to alienate a lot of newplayers. The layout alone has 50 million things you need to understand and keep track of. When you DO get into it though, it's an absurdly beautiful, original, deep and solid fighter to the point of being playable poetry. If you saw EVO this weekend you'll understand.
SF, on the other hand, remains my favorite, and the benchmark for all other fighting games. Every noob can hop in and start pulling hadokens and shoryukens after 5 minutes (half an hour if you're REALLY inexperienced in this type of games in general). Mastering the game? Get ready to spend years on it and never be done. It's the epitome of "easy to pick up, hard to master". 2 newbies can pick up the game and in a couple of hours start having actual fun using special skills, maybe pulling basic combos, etc. But the more you play the deeper you go, the more depth you find. Combos, frame data, hitboxes, match ups, FADC, canceling, frame traps, resets, kara throws, setups, option selects, linking, plinking, input buffering, negative edge... it goes on.
Yes, in those games, a pro will absolutely DESTROY a newbie. I'm talking, and to use SF terminology, "double tokyo bananaed", "completely bodied", levels of trashing. But... Isn't that true for any other decent game (videogame or otherwise) ever? Experience beats inexperience? Knowledge beats ignorance? That's what separates good games from bad games: The skill roof. The potential of a player to grow and attain better results based on his own skill.
