I know exactly what you mean my friend!
Hmm... SNES style huh, how about
Secret of Mana (One of my Favorites)
Secret of Evermore (Haven't played to finish but based on same engine as SoM above.)
Seiken Densetsu 3 (Secret of Mana 3. You'll have to look on DeJap for the translation.)
Might & Magic 3: Isles of Terra (I have this for DOS but also on SNES.)
7th Saga (This might be the one you were talking about.)
Playstation 1
King's Field (First person 3D hack and slash rpg. NO loading times. 2nd installment of the series. My all time favorite series.)
King's Field 2 (3rd installment of the series same engine as the one above.)
Shadow Tower (Spinoff of King's Field series but not as good.)
Breath of Fire 3 and 4 (Yes random encounters but still two of the best RPGs.)
Lunar: Silver Star Story (Selectable encounters like Star Ocean for PS2 great game.)
Jade Cocoon (Selectable encounters.)
Legend of Legaia (Random encounter but nice battle system.)
Playstation 2
Final Fantasy 12 (One of my favorites regardless of the story just because it has open world battles. I just imported the Zodiac Job System version, now I have to learn Japanese.)
King's Field: The Ancient City (4th installment of King's Field series. Still 3D first person hack and slash style.)
Star Ocean: Till the End of Time (Battles are only initiated if you run into an enemy on the map.)
Kingdom Hearts (Haven't played to completion but still fun. Open world battles.)
Legaia 2: Duel Saga (Like Legend of Legaia.)
Drakengard (More action less RPG but still not bad.)
Commodore 64
http://www.newcomer.hu/ (I haven't played this one yet because the new version isn't out yet but its supposed to be a huge game 20+ years in the making.)
Sega Mega Drive/Genesis
Shining in the Darkness (It kinda has and doesn't have random encounters. At least not the swirly screen battle music kind.)
Buck Rogers: Countdown to Doomsday (AD&D Goldbox Engine game. DOS version has better mechanics Sega version better graphics. Many hours were lost to this game.)
PC DOS/Win
Gothic 1 & 2 (Great games I highly recommend the first. Kinda plays like a console game.)
Nethack (Who can forget this 'killer' of a game. The only one I know of that laughs at your repeated deaths.)
Any Might & Magic game accept IX (You can find them all on GOG.com accept IX.)
The Elder Scrolls: Arena (Think you can still download from Elder Scrolls website.)
The Elder Scrolls: Daggerfall (Same with Arena.)
Diablo
Diablo 2
Nox
Deus Ex (Love it.)
Fallout 1 & 2 (Hybrid turnbased overworld battles. Still great.)
Syndicate (Control a team of four cybernetically enhanced operatives and buy upgrades throughout the game. Also for AMIGA)
FATE (From Wildtangent games, basically a Diablo clone. Still not bad.)
The Witcher (Great game. The book is also great.)
Dark Messiah of Might and Magic (Modern 3D first person hack and slash game. Great game.)
Thief Series (Not RPGs in the literal sense but still very fun if you like stealth games.)
Cannon Fodder (Not an RPG but still a fun game.)
Well I think this list could keep you busy for quite a while. I'm also out of games to list (well I have left out some more obvious ones).
Congrats on graduating!