You probably won't need to watch all the videos, but there are a bunch that make for good introductions (and some that are very clear guides on implementing) various programming concepts and systems. The annotated episodes are a great way to learn individual things, but there's value in just listening to episodes more-or-less in order to just pick up on how the project is put together and Casey's wisdom of the subject.
Making an engine from scratch in Python or C# is tricky, since you have to bind to the OS level interfaces yourself. Python has a FFI system which lets you call C from Python with relative ease, and C# (and the rest of .NET) has DllImport, which achieves mostly the same goal. If you'd rather write most of the code yourself, there exist bindings to SDL2 for both Python (PySDL2) and C# (SDL2-CS). However, if you want to get right up to the metal, C/C++ is the way to go. You can still using a layer like SDL2 and get decent results, and it's easier to use from native C than through a wrapper in Python or C#, but you are giving up some control and using someone else's assumptions.
Your premise is fine, but I don't think you're matching your fantasy with your planned gameplay very well. A ninja returning home was successful, right? He must have practiced until he was a master at acrobatics, combat, etc. If he's so good, why is the game hard? Not that the story is particularly important to that kind of game, but as a game designer, you need to identify what your audience wants out of your game and what you can deliver on. It's clear that you want your game to be exciting and fun due to its challenge, but the implementation matters; for example: do you want to feel strong and powerful, "solving" combat situations with improvisational fighting skill? Or do you want to feel accomplished by carefully working out enemy placement and learning how to execute the singular solution to a level?
Not to say that you can't build your game incrementally, only following your preferences at each step, but if you care about cohesiveness in your tone and mechanics (which is generally the aesthetic games aim for) and avoiding wasted design and implementation, it's worth thinking about the balance of things that go into platformers and similar games before you start building stuff. Consider this list I pulled off the top of my head: Castlevania (both original and SotN/Dawn of Sorrow styles) Kirby (Nightmare in Dreamland), Mario, Metroid (Metroid 2, Super Metroid, Fusion, Zero Mission), Super Meat Boy, Shovel Knight, 1001 Spikes, VVVVVV, Spelunky, 140, Risk of Rain, Cave Story, Binding of Isaac, Braid, Bastion, Downwell, Dustforce, Eryi's Action, I wanna be the guy, Mark of the Ninja, Castle Crashers, FEZ, and Rogue Legacy are all games that capture some portion of what you've described. If you broadly group them into some categories: "thinking" (VVVVVV, 1001 Spikes, 140, Braid), "fighting" (Bastion, Cave Story, Binding of Isaac, Downwell, Mark of the Ninja, Castle Crashers), "challenge" (Meat Boy, Eryi's Action, I wanna be the guy, Dustforce, Mario), and "explore" (Metroid, Castlevania, FEZ, Isaac and Risk of Rain to an extent), where do you want your game to sit? Not to scare you into paralysis and overdesigning--there's no way you can have some set-in-stone balance of elements a priori; game design is an art that's implemented iteratively through cycles of playtesting and refinement. A vague feeling of what you like in each area plus what you find easy to implement will probably guide you to a good final design, but it's important that you realize that you are making decisions that impact that with every decision you make: from high-level tonal ones like above, to more concrete ones ("how linear are my levels?", "backtracking?", "weapon/equipment customization?"), your choices end up making the final game.
Lastly, difficulty is very easy to tweak, but the fundamental nature of the game you've built isn't. To make something harder, make the player do more work faster; take Simon (the box with colored buttons on it): it gets harder because you're forced to make process the moves you need to make faster and faster. It's old, fair and challenging--should be the perfect game, right? I think a lot of people would call it boring compared to Megaman or Castlevania because it doesn't deliver on narrative or fantasy, and the nature of those elements are tied to how you build your game out of levels, monsters, weapons, powerups, and everything else. Focus on what you want your players to feel, then tune the difficulty until it becomes exciting.
Recommended media:
Even if you don't like what they make, this short video Apple made for one of their conferences hits on the fundamentals of design: "...requires focus... the first thing we do is ask 'what do we want people to feel'... there are a thousand no's for every yes..." Not sure how much design work you've done before, but this is it in a nutshell. Worth analyzing in relation phones (which is where the joy/convenience, abundance/choice tradeoffs in the beginning make the most sense).
"Intention":
https://www.youtube.com/watch?v=nmV3KMniZuQ
Mark Rosewater has worked on Magic: the Gathering for a very long time now. While most of what he discusses are geared towards multiplayer, they're often important to think about in single-player too.
"10 things every game needs":
http://magic.wizards.com/en/artic...me-needs-part-1-part-2-2011-12-19
"20 years; 20 lessons":
https://www.youtube.com/watch?v=QHHg99hwQGY
I didn't talk about game feel in this, and while I'm not particularly excited about the game he's showing off, so much of what makes an experience exciting is up to the game feel, animation and music.
"Why your death animation sucks":
https://www.youtube.com/watch?v=pmSAG51BybY
Extra Credits did an episode on what makes a game hard but fun instead of infuriatingly punishing.
"Extra Credits: Hard v. Punishing"
https://www.youtube.com/watch?v=ea6UuRTjkKs
Books:
The Design of Everyday Things
Understanding Comics
Alright... I've been working on this at some stupid hour in the morning; sorry if parts don't make sense. Best of luck with your game.