Since I started speedrunning properly last year I've dabbed a toe in platforming with Flimbo's Quest, run and gun with Mercs, pure puzzle stuff with Lemmings, and sport stuff with Super Hang-On. I'm looking to get a capture card at some point so I can also run The Unholy War. These haven't really been optimised run at all before - there's something extra special about exploring and uncovering the secrets behind how a game works, how to optimise it, being the discoverer as well as the runner.

These games have a very well-defined strategic element, you can definitely imprint your style on to them in terms of what choices you make, and in which optional paths or methods you use to achieve your aims.

I looked through the list of all the games I used to play/own several times though, and nothing stands out as particularly well-made/interesting for speedrunning. As a crude example I had looked at something like Zool or Global Gladiators, but they seem quite inaccessible (the former for its controls and camera, the latter is just a horror show to run fast). It would be nice to end up running something Nintendo but frankly anything from C64 to PS1/N64 I'm open to as long as it's relatively unexplored and strategic, and not massively long - I could be comfortable with anything up to an hour maybe. The one proviso I want to impose on this is no excessive menuing. I was going to jump into Wonder Boy in Monster World but I honestly hate the idea of losing records based on menuing alone.

Can anyone make any recommendations of games they know and love which have some strategy and similar traits to the games I've played, and which haven't really been explored as far as being run?

I'm not really seeing a common theme in the games you've chosen to run. Keep it up though, I think you've selected a nice variety.

Here are some Game Boy games that don't currently have runs, but might have some interesting strategies to explore:

Crazy Castle series -- no runs of 4 and 5 yet Cyraid Lock n' Chase Solomon's Club Ultima: Runes of Virtue 2

I've started running games from the NDS era, and I know what you mean about losing time to menuing. Without being really fast with a stylus, losing time is incredibly easy in the games I've been practicing. (This is excluding the fact that one of them is likely going to take 7+ hours to run.)

C64 to N64 is a pretty wide range, but I'm trying to think of the games from my childhood that would match your requirements. I was almost exclusively a Nintendo player when I was real young but most of the games that come to mind are pretty popular, so I'll just do the more obscure ones.

These are all from the NES era: Mendel Palace- I experimented with running this before and its only got a few runs. A very fun, (potentially frustrating,) and mostly forgotten puzzle-action game by GameFreak, the folks who later became famous for Pokemon. 20+ minutes long once you know the run. Sword Master- It's hard on your hands, but it can be rewarding. Pretty much explored already, though. Can be done in as short as six minutes. Adventures of Lolo 3: Less runners compared to the earlier ones, but takes a little more than an hour. I don't remember that much about the game, it's been forever.

If you want something 3D, there's always Quest 64. It's got a couple of runs and it's probably been explored, but I remember it as an interesting game. It's kind of long, though. I'd suggest Phantasy Star 1-4 (Sega systems) or the Ultima (NES and DOS) games, but I know there's a chunk of menuing given that they're RPGs and some of 'em are long.

You could also check out Zeilard, its a MS-DOS game made around the same time the NES was released, and its a rather impressive game considering that. Nice soundtrack, graphics, fluid gameplay, and it's not even on this site. I just play it every once in a while for fun, but I've considered running it. I don't know about the length as I haven't finished it yet, but I do know that it used to have some dedicated followers back in the day.

Like yourself I am someone who enjoys creating and exploring new games to create speedruns for so trust me I know how you feel. Anyway I can think of a few interesting games that might work for you but they don't seem to meet all of the different things you're looking for but each do hit some. Anyways:

Robin Hood: Prince of thieves (NES) t's based on the movie from the 90's and is an interesting top down action RPG. There's only really been 1 run from years back and is under an hour.

The Pagemaster (SNES): It's based off the movie and is s platformer. It's actually been on my own list to explore and see about creating a speedrun for. It's got some interesting things and could make for something fun.

I'd also recommend looking into any of the licensed games, as well as some of the handheld versions of games. Mind you I'm not the best speedrunner myself but I can offer at least 1 piece of advice, find something you think might be fun as a speedrun or that you think would be interesting to figure out and route. Even if you don't ever speed run the game it's always worth exploring how it could be do. Besides getting someone interested in trying new games is also part of speedrunning.