The Nintendo 64 games were not the only ones with a good story, but I do believe they are the best in that regard (and among best overall)
I mean, stories in Super BMan games were simplicistic but I surely enjoyed them.
...and am I the only one noticing that spider boss is from the final battle of Super Bomberman 1? Or was it just too obvious to state?