Don't know what to call this genre. Non-linear side-scrolling adventure?

The first: Metroid
The formula: Super Metroid
The definer: Castlevania: Symphony of the Night

2D fighters:
The first: No idea. Street Fighter 1?
The formula: Street Fighter II
The definer: Probably up for debate but for me it's Marvel vs. Capcom 2. I feel it's the standard.

2D platformer:
The first: Pitfall?
The formula: Super Mario Bros.
The definer: Super Mario Bros. 3