Science Fiction? I always considered it a 'subgenre' of fantasy...

Hard question! Most games I play are fantasy... There's also the crossover; how many 'fantasy elements' should be present in game to be allowed in the fantasy genre? (I'm thinking... what about Max Payne?) ;-)

Well, as you pointed out, many games have fantasy elements, but I am looking for more "traditional" fantasy... yet, space fantasy is ok (ie Star Wars).

What does Avernum/Exile count as?

I happen to like common magic settings, where the ability to use magic isn't an exotic and mysterious factor, but rather is commonplace and the inability to use magic, if present in any character, is rare enough to be a plot point.

I also think it can be interesting to mix future technology into the mix, though I prefer it not to interfere with magic.

One other requirement: At least some of the playable characters need to be able to use magic, otherwise I am significantly less interested.

Warhammer is probably one of my favorite places to be in fantasy, dark depressing, ridiculous size and comes both in fantasy and in sci fi flavor

Dungeons and Dragons ( and companions ) also has that special ring to it.

I like setting, story and atmosphere in Planescape: Torment and VTM: Bloodlines (if the latter still counts as fantasy).
I like setting, story and combat in the Shadowrun trilogy.
I like atmosphere and exploration in Arx Fatalis, Blade of Darkness, Gothic/Gothic 2/Risen, Nehrim/Enderal, Enclave, Heretic.
I like atmosphere and combat in Dark Messiah of Might and Magic.
I like dragon riding in Drakan: Order of the Flame and Divinity 2: Ego Draconis.
I like combat, exploration and quests in the Divinity: Original Sins, in Baldur's Gate 2, and maybe Pillars of Eternity and Dragon Age: Origins (not so fond of the story-telling in D:OS and PoE though; much ado about nothing).
I like dungeon crawling in the Dungeon Master, Eye of the Beholder and Legend of Grimrock series, as well as Lands of Lore: The Throne of Chaos.
I like all the creativity in fan made modules for Neverwinter Winter Nights 1 & 2, Forgotten Realms Unlimited Adventures, and - on a much smaller scale - Fight the Dragon and Dark Quest 2. Maybe, maybe Popup Dungeon, too. Oh, and mods for DOOM and DOOM 2 (they are kind of fantasy-themed, too, for the most part).
I'm usually not much of a fan of Diablo-style ARPGs, they're alright, but often get pretty repetitive after a while; yet I did like Nox back in the days, for its slightly different, more arcade-y and story-focused approach, shorter length and varied content based on character class (haven't played it in ages though). And with regards to an average young boy being the hero in a fantasy game, I also liked Heart of Darkness and Driftmoon.
I like short, card-based rogue-lites with fantasy setting like Hand of Fate and Slay the Spire.
I like the puzzle platforming in the Trine games.
I like the original setting and characters of the Oddworld games.

Never been much of a fantasy fan, but I did enjoy Warcraft III and World of Warcraft. Something with the lore, story and world building stuck with me I guess.

I like the Castlevania games if more gothic style games count too.

Betrayal at Krondor for the feeling of playing a book.
Divine Divinity as an ARPG.
Evil Islands for the crafting system.
Gothic 1 & 2 for the atmosphere and world.
Heroes of Might and Magic 4 for being what I always wanted that series to be.
King's Bounty: The Legend as TBS, if I was to just pick one.
Knights of the Old Republic 1 & 2 for characters and what they did with the Star Wars concepts.
Might and Magic 6 as a blobber.
Planescape: Torment for the writing.
Quest for Glory 2 & 3 as adventure-RPGs.
The Spirit Engine 2 for a freeware one-man project with an amazing amount of polish and attention to detail.
StarCraft: Brood War as RTS, but maybe more for really creating Kerrigan as a character.
Vampire: The Masquerade: Bloodlines for the atmosphere, writing, dialogues, some characters...
The Witcher 1 as a labor of love and for how the combat flowed.
Two Worlds 1 for the exploration and varied world.

Not overly familiar, but it seems suitably fantasy.

I'm not trying to make any hard-and-fast rules / "boxes"... just generally... if you went to the store looking for a game, it would probably be on a shelf labeled "fantasy" as opposed to "mystery" or "crime" or "action."

My favorite fantasy videogames would probably be:

Dragon's Dogma. The game that got me into fantasy, a genre that I actually disliked prior.

Blackguards 2. A Dark Eye game that turned me on to turn-based combat -- yes, another genre that I had disliked prior.

Greedfall. There are some hard edges and a lack of polish, but I loved the game.

God of War. One of the most affecting stories I've played... and gorgeous to look at.

I'm sure there are a few Tolkien games I could add to the list if I thought longer on it... and certainly a lot of AA and indies that almost made it. And having just gotten into Warhammer, we'll have to see...

The Legend of Zelda: Link's Awakening (GB, 1993)
It's pretty amazing what Nintendo eventually managed to pull off with the original GB hardware after much simpler earlier titles. Case in point, Link's Awakening which translated the gameplay, mechanics and overall look of the SNES game near perfectly given the limitations, while also adding to the experience with stronger worldbuilding and major additions like platforming in two perspectives, as well as often more complex, distinct and tighter designed dungeons.
I also think LA has one of the most interesting settings in the Zelda series besides Majora's Mask in its fleeting island-based dream world with surreal elements like the dream fish and phone booths, and a sort of wistful and ominous tone throughout much of it. The latter really gels with how the story turns out and the limitations of the GB hardware, somehow turning them into a strength rather than a weakness.

Baldur's Gate (PC, 1998) & Tales of the Sword Coast (PC, 1999)(Expansion) - BioWare & Black Isle Studios

Super Mario Bros. 3 (NES, 1988/SNES, 1993)
SMB3 is an excellent all around package with a compelling world, great controls and great variety while also having more depth than its prequels. It's a large game that is also filled to the brim with neat stuff like the hidden warp flutes, wandering enemies on the map and secret map encounters, especially for a 1988 NES game. I don't think later 2D Mario games have topped it in terms of worldbuilding, hell the New series doesn't even come close.

Rocket Knight Adventures (MD, 1993)
RKA! This game is a smörgåsbord of all things I love about Konami during this era: fast and tight movement, great variety with a couple of shoot 'em up levels mixed in as well as a boxing duel between two giant robots, great bosses that sometimes have multiple forms or phases, great audiovisuals with some humorous touches, and near technical mastery of the system all in one package.
The jetpack, while implemented slightly better in later games, is great fun to use here as well and sometimes makes the game a contender for the fastest playing 16-bit game if you know the levels well. By the way, check out Screw Attack's Retro vs. Reboot for a laugh.

Super Mario World 2: Yoshi’s Island (SNES)
Heroes of Might and Magic III: The Restoration of Erathia/Heroes 3 (PC, 1999)

Wonder Boy III: The Dragon's Trap/Monster World II (SMS, 1989/PC, 2017)
My fave 8-bit game after SMB 3 and still one of the best MV/Platform Adventure games if we include later versions and fan remakes. Excellent presentation, the forms are distinct and fun to use, great pacing, and cool secrets like being able to switch or create platforms anywhere. There's even some non-linearity in the dungeon order if one so prefers. Last but not least this is also where the whole "beginning of the game ties into the prequel" trope comes from afaik, which was later used in Symphony of the Night.

Langrisser II (MD, 1994)
When it comes to SRPGs I think this is as good as it gets for the MD and the 16-bit gen, and the game outshines its prequel (Warsong) with its improved character customization, balancing, AI and variety. Langrisser 2 offers a very challenging game (dead characters stay dead), huge battles, cool classes like Summoner and Dragon Knight, a decent story with a lot of humour and twists, and excellent music. Still only playable in English via emulation, but you'll probably want to be able to fast forward after a few battles anyway. Also: Chou Aniki cameo.

Mother 3 (GBA, 2006)
Itoi's writing is in a league of its own and it's both more mature and better translated here than in the prequel; witty, funny, quirky and sometimes quite touching. Gameplay is also good with a fun rhythm gimmick to battles and while it's mostly linear, it works better for the story and pacing I think. The 2D pixel art and an eclectic lo-fi pop/funk/rock/orchestral mix aesthetics are timeless.

Panorama Cotton (MD, 1994)
It's pretty odd that this game even exists for the stock MD. Success, a game company that never made anything for the console prior to this (though I think some devs come from Compile), decides to turn Cotton into a Space Harrier-like shooter, make it one of the most technically impressive efforts for the system, then release a limited amount of copies exclusively for the Japanese market as late as mid-1994. Well I'm glad they did, because they certainly _succeeded_ in making Panorama Cotton an amazing game (for example you get branching paths and RPG elements years before PD Zwei here) and something of a swan song for the 2D-based rail shooter. Now if someone would port this to the MCD for super smooth scaling...

Wario Land: Super Mario Land 3 (GB, 1994)
Seirei Senshi Spriggan (PCE CD, 1991) - Sci-fi mix
The Typing of the Dead (ARC, 1999/DC/PC, 2000)
Saturn Bomberman (SAT, 1996)
Warcraft II: Tides of Darkness (PC, 1995) & Warcraft II: Beyond the Dark Portal (PC)(Expansion)
The Legend of Zelda: A Link to the Past (SNES)

Alex Kidd in Miracle World (SMS, 1986)
This takes hacks/mods into account however it's still a top 10 game without them. AK1 was an ambitious platformer for its time with an inventory system, shops, dungeon levels with switch puzzles, optional side quests and unique quirks like how you remove the ghost enemies via blocks that make it still stand out today. It's disappointing how even Sega fans in the US dismiss this one as a SMB clone when there's a lot more to it. The one thing that doesn't hold up, janken, isn't even that prominent in the game.

Donkey Kong Country (SNES)
Donkey Kong (GB, 1994)
Monster Boy and the Cursed Kingdom (PC, 2018)

Age of Empires II: The Age of Kings (PC)
Warhammer 40,000: Dawn of War & Expansions (PC) - Sci-fi w/ strong fantasy elements
Final Fantasy VII (PS1, 1997) - Mix
Mole Mania (GB, 1996)

Landstalker: The Treasures of King Nole (MD, 1992)
This game can stalk my land any time. Landstalker is... quite a bit like Zelda 3 if it was an isometric view game, but with an actually interesting story (not the usual damsel in distress and save the world thing with a silent protag), a less formulaic structure, and more challenging puzzles. The lack of a shadow when jumping and some other control quirks were only a minor annoyance for me, since I used save states hehe.

Baldur's Gate II: Shadows of Amn (PC) & Baldur's Gate II: Throne of Bhaal (PC)

Yu Yu Hakusho: Makyou Toitsusen (MD, 1994)
Was gonna put Mega Bomberman on the list but assuming we're doing PCE/TG16 (this was copy-pasted from another thread) I can mention this one instead. Growing up we used to play the 3-player fighting game International Karate+ on a buddy's Amiga a lot, and we loved the sheer chaos of it. So in the '00s when I discovered that this game had the same feature but with yet another player added, I had to play it. And (spoiler) Treasure did it once again, it's a great fighting game in the vein of Fatal Fury 2. Matches might not be as fair or precise as in Street Fighter 2 when you play like this, but the laughs from unintended results and the fun in temporary alliances make up for it.

Land of Illusion Starring Mickey Mouse (SMS, 1993)
Pocky & Rocky (SNES)
Fantasy Zone II DX (ARC/3DS) - Mix
Shining Force II (MD, 1993)
Panzer Dragoon II Zwei (SAT, 1996) - Mix
Dragon's Curse Remake (fan remake of WB3)(PC, 2008?)
Dungeon Keeper (PC)
DuckTales 2 (NES/GB, 1993)
Castlevania: Circle of the Moon (GBA, 2001)
Terranigma (SNES, 1995)
Lunar: Eternal Blue (MCD, 1994)
Virtual Boy Wario Land (VB)
Ganbare Goemon 2 (SNES)
Soul Blade/Soul Edge (PS1, 1996)
SoulCalibur (DC)
Secret of Evermore (SNES)(w/ mods)
Castlevania: Symphony of the Night (PS1)
Lords of Thunder (PCE CD, 1993/MCD, 1995)
Crystalis (NES, 1990)(w/ mods)
Lunar: Eternal Blue (MCD)
Solomon's Key (NES/ARC, 1986)
Chrono Trigger (SNES)
DuckTales 2 (NES/GB)
Castlevania: Rondo of Blood (PCE CD)
Castlevania: Bloodlines (MD)
Super Castlevania IV (SNES)
Final Fantasy Adventure/Seiken Densetsu (GB, 1991)
Ghouls 'n Ghosts (ARC, 1988/MD, 1989)
Final Fantasy V (SNES)
Gargoyle's Quest II: The Demon Darkness (NES, 1992/GB)
Gargoyle's Quest (GB, 1992/GB)
Warcraft III (PC)
Kirby's Adventure (Wii)
Kirby Super Star (SNES)
Dungeon Keeper 2 (PC)
Adventures of Lolo 1-2 (NES)
Sylvan Tale (GG)
Hamelin no Violin Hiki (SNES, 1995)
Populous: The Beginning (PC)
Solomon's Key 2/Fire & Ice (NES)
Strife (PC) - Mix

Arcanum - Just a great blend of the Steampunk universe and classical fantasy universe.

Yeah, just wading into Warhammer (fantasy) now.

Way too long a list, many of which I never or at most barely heard of, to see if there aren't others I'd ask the same about, but... that's fantasy? Sure you didn't mean Age of Mythology? Wouldn't say so. SF must be based in science and function according to the laws of nature in this universe, be plausible within those confines. Fantasy must only be internally consistent, function according to its own laws, in its own universe. When you mix the two, as in Star Wars, you have science-fantasy, which would fit here.