Maybe you should try some 16 bit gaming before you knock it^^

Sheesh, Earthbound was recommended a lot already, but that's good! Because you should play it. It doesn't have any random encounters, and it even has a rolling HP system, which is pretty sweet :3

If you have a PS1 check out Vagrant Story (released in 1999) as well, Fallout 3's battle system is highly remeniscent of VS' in fact it wouldn't be surprising if they were inspired by it and "borrowed" the idea as you can move around in realtime and see your enemy, press the action button to freeze time and select certain body parts to attack. Targeting specific body parts will yield certain results (attacking legs will impede movement, attacking arms lowers weapon wielding strength,ect). Altogether a very fun game that was ahead of its time.

People already said Evermore and Earthbound. Front Mission and Bahamut Lagoon are a must if you're a fan of the genre, but they're SRPGs.
And while we're on the subject, what's wrong with random encounters?

Vagrant Story best rpg ever

Amen Jonager.

I could never get into Evermore.

I hate the idea of Alchemy. :(

First of all. You aren't going to get many replies to your question. Because the SNES didn't have many RPGs without random Encounters. The system both wasn't strong enough to support large amounts of sprites on screen and the carts space didn't allow for large amounts of data. Only last gen games which were 32 Bit were able to push that envelope. Games like Chrono Trigger, Seiken Densetsu 3 and Terranigma. Secret of Mana was a good experiment, but as you surely found out by playing it, it had tons of glitches, lagged often when more than a few enemies were on screen and response time for your own character was slow. Because it was an earlier SNES game.

So, the 'non' Random Encounter games had to wait for a more powerful system.

This means most of the RPGs on the SNES have Random Encounters. But that doesn't make them bad. In fact, the same guys who made Chrono Trigger made probably the best RPGs on the system after Chrono Trigger. Dragon Quest V and Final Fantasy VI.

Chrono Trigger has random encounters.  Give Knights of the Old Republic a try.  Its turn based and its really good.  The story and voice acting is movie quality imo.  Easily one of the best games i've ever played.

 Actually, no, it doesn't. All the enemies are in pre-set locations. I think pretty much anyone could tell you that. Nice try though.

Neither did Earthbound. :3

        Secret of Mana 2 is great (it's called Seiken Dentetsu 3 in Japan I think), though the combat feels a little different from the first it's basically exactly the same combat system. There's also an old SNES RPG called Robotrek, I think, which has you playing a young inventor boy in a modern world similar to earthbound. Your robots fight in battle, and instead of leveling up you design and upgrade them. It's a really good game that does a lot of things different but still feels polished. The enemies walk around on screen like in Chrono Trigger. Earthbound is also awesome. Haven't played that one in years. You pick your favorite food in the beginning, and some other stuff.

        If you're willing to go a bit newer, you should definitely try the Grandia games. It's a great series (with no random encounters), and the third one has probably the best jrpg combat system ever (possibly better than Chrono Trigger's pure awesomeness). The only problem is that the story of the 3rd one goes downhill fast!

        I never had a PS1 but I just played Vagrant Story recently and it's pretty good -- also recommended. There's also Legend of Mana, which can be as fun as the old Manas except it isn't tied together as well over a whole story.

        If you're ever looking for a new RPG that feels like a really god 16 bit RPG, try Tales of Vesperia for the 360, it's a great game, and if you want it has decent multiplayer in battles.  The enemies are visible in the field, like in Chrono Trigger (and most of the games I've named).

        Hope you like whatever you end up trying,

Alic