Thanks for all the suggestions! Now I have completed games without a guide before but those were not RPGs. Then again, I can't say that RPGs have bad game design always after seeing this list.
FF7, sure, its popular and overrated, but the design isn't the best. After you leave Rocket Town, you get the Tiny Bronco, the game tells you to go to the temple of the ancients but you're really supposed to go to the gold saucer. You can figure that out by exploring everywhere which is fun and puts the exploration into the game.
But yeah, exploration is pretty fun too. I might try out FF6.