Just Fate stay night and Steins Gate...
I'm not quite sure all the types of novels, so just throw some names at me and I'll check them out
First off, I might recommend Tsukihime jusat for the sake of completetion.
Tsukihime makes up the second big half of Nasu's works.
If you read this and FSN you get a much better gist of the Nasuverse.
Tsukihime is a supernatural murder/horror mystery story.
It has lot of suspense and secrets. No one, not even the protagonist, is who you'd initially believe them to be.
In terms of actual plot I believe it beats FSN. Even if I like FSN better.
The problem is that Tsukihime is Type-MOON's very first game and it was made when they were only considered a doujin-soft company.
(Needless to say, this game is what managed to change that soon.)
Which means its visuals are rather dated and the BGM is generally just so-so. (If it even works on your computer, so I suggest listening to something else while playing this.)
Still, I do recommend this to you.
Okay, that was the obligatory advertisement. Seeing this is a TM forum.
Other suggestions, based on the two VNs you played and what little I remember:
This is a survival and Sci-Fi mystery.
The basic plot is that a group of people get trapped in an underwater entertainment complex after it suffers a weird accident.
You can choose one of the two protagonists and several routes as they are trying to find a way back to the surface.
Doesn't sound too ambitious but the looks can be deceiving.
I called it a Sci-Fi mystery with reason, afterall.
The execution is also pretty great. You get drama, suspense and decent amount of character development.
And there's a final route which finally puts every little piece together. And how!
If you liked Steins;Gate you'd most likely enjoy this too.
And I personally rate Ever17 higher.
Albeit you'd only realize this mid way.
Muv-Luv starts out as a fun but classic Harem/Dating Sim game.
And then you realize this is technically 3 games:
Muv-Luv Extra, Muv-Luv Unlimited and Muv-Luv Alternative (you have to get the last one as a separate game because the devs couldn't finish Alternative in time)
Like I said Extra is a romantic comedy.
But then our protagonist is suddenly drawn into a post-apocalyptic alternate reality. This is the start of Unlimited.
Think of a more bleak and dark version of Gundam with elements of military thriller.
Takeru becomes a cadet and slowly drilled into a soldier while understanding and settling down in this new world.
Still, that would only make Muv-Luv average in my book.
But then the previous two games are only a build-up for the last part, Alternative.
It involves Takeru trying to save the world.
But becoming a hero is no joke and Takeru had to learn this the hard way.
Every action of his drew unforeseen consequences.
Great progress were made at the cost of similarly huge sacrifices.
Diabolus Ex Machina to ensure anything that can go wrong WILL go wrong.
And through these failings and tribulations Takeru gradually changes into a man.
He steels himself and learns the real meaning of responsibility.
In this sense I can call this Heavens Feel turned up into eleven.
Of course, if anything, Alternative also has tons of mecha action, warfare, politics, intrigue and some Sci-Fi styled mystery.
And heroics. Lots and lots of heroics. It's like everyone including their mothers are secretly heroes waiting to bloom.
Muv-Luv Alternative, especially its second part, is very intense.
At times the plot is downright cruel, especially from the protagonist's viewpoint.
It isn't for the faint of heart, I suppose.
But I believe this all worth it.
G-Senou no Maou
This is a detective mystery/action story.
Basically it's a cat and mouse game between the protagonist and the enigmatic terrorist Maou.
Lots of plotting, wits and suspenseful situations.
Of course there are also certain betrayals and twists.
The characters are entertaining (especially Haru) but save a few they'd need more fleshing out.
That's what I could gather.
This game is on my list since a while but I have yet to garner the time to play it.
Hope it helps.