Tallima: I'll have to try Mario again some time. I tried it a few years back and still couldn't beat it. I'm just terrible at it. I have to admit that I go straight to 8-1 as fast as possible, so it's likely that I need to play more levels to get more 1-ups to get through it. I really should give it a go again.
I'd say using the shortcuts is definitely the easier ( and cheaper ) way of beating the game. You might miss out on those 1-ups, but you'll also be able to skip many of the harder stages along the way. I don't know, I remember it as one of the easier games, by NES standards. But I'll admit some sections can be hit or miss, and require a bit of luck to make it through, in particular the Bowser "boss fights" at the end of each castle.
If you're not adamant about getting the full retro experience, I'd recommend the SNES Super Mario All-Stars version of the original Super Mario Bros. I'm fairly sure it has the same level layouts, but is a lot nicer to look at.
Tallima: As for Dark Souls, I beat the gargoyles (only the 2nd boss I think). I played a sorcerer for my longest play-through (I tried a few other classes without success). After that, I got to a bunch of places where everything killed me super-fast and I couldn't kill anything. I figured that I must have been missing a place, but I couldn't find it.
The thing about the Souls games is, I usually start out with a specific class or playstyle in mind, but in the end the game always "forces" me in a completely different direction. In other words, it's important to adapt to the various challenges the game provides, which is why I usually end up with a "Jack-of-all-Trades" kind of character. Probably bad for PVP, but for the main game and boss battles it's a great advantage if you're able to switch between magic, archery or melee combat, depending on the situation. ( Plus, I think it's more fun that way, too. ) And if all else fails, there's tons of guides and strategies online, to make things easier.
By the way, it seems to be quite common that people give up on Dark Souls, but then come back after a while to give it another try, and in the end they completely love it. The first few hours are probably the toughest, especially when you've never played a game in the series before. But once you get the hang of the basic gameplay features, combat etc., defeated a few bosses, and found some better equipment and spells -- well, it's very satisfying and addictive. :)