I agree that starting with mechanics is the necessary first step. I have seen some games where the mechanics made me entirely uninterested in proceeding past the tutorial or very early game and others where the mechanics made the game worse the whole time but not completely unplayable. Maybe I see games unplayable due to mechanics about as often as I see games unplayable due to technical issues (as someone who generally does not buy games when they are first released).

It seems to me (without having actually designed games) that level design and the story can be done with basic artwork and sound and that making sure that stuff is great before spending a bunch of money on artwork would improve things.

I wish developers would avoid violence as a core theme of games. There must be other themes you can use even with the same basic mechanics.

Good luck with your game! I really love story driven games and there are so few good ones.