You can go a lot of different ways with fantasy/Sci-fi, would be better if you gave specifics as to what type of fantasy/sci-fi you were looking for. The list would be too long trying to describe all the good VN in these general terms, so I'll just give some medieval fantasy suggestions and let other people cover the other areas. Pretty much every great translated medieval fantasy VN has gameplay mixed in.
Kamidori's main draw is the gameplay. It's still a fun VN, but if you're wanting to play a TBS for the story, then Tears To Tiara would be my first suggestion with Utawarerumono following in a close second.
Alicesoft titles are pretty much the tops for fantasy worldbuilding, but they are all very gameplay heavy and they are known for comedic rape in their H-scenes.
Duel Savior and Brave Soul are both more standard RPGs with animu plots/characters. Neither would be my first suggestion for story, but Duel Savior is the better choice on that front.
LittleWitch Romanesque has a lot of fantasy to it, but a rather strange dice rolling gameplay.
Koihime Musou's gameplay is simple but difficult to describe. It's another option.