I fail to see how something like Grandia 3 could be considered a button masher seeing as how it's turn based and just spamming the same attack over and over isn't going to get you far. Tales of Symphonia? Sure. Grandia 3? Nope.
Moreover, if a game is really fun to play, it doesn't need a story. Does a game like Civilization have a story? Not really; it's still one of my favorite games. People love the Mario games despite the fact that the story rarely gets more advanced than rescuing the princess. Tetris and other puzzle games like Bejewelled remain highly popular despite their absence of stories.
I have run across the "Gameplay doesn't change and so I eventually get bored of it" problem. Magna Carta is an excellent example. At first, I loved the game: it had several interesting systems with a decent amount of depth. However, by around the 15-20 hour mark, I felt like I had mastered the game's systems and things started to really drag. On the other hand, with Grandia 3, I'm yet to run into this problem. Some features of the gameplay like skill & spell extraction and mana egg combining don't show up until later. Moreover, skills steadily become more and more important as the game goes on as you find more impressive skills & gain enhanced skill books. As an example of how this changes things around, I'm about 2/3s of the way through the game and I just discovered a skill that doubles item power when maxed out. Because of that skill, I've gone from virtually ignoring items to having explosives figure prominently in my battle strategies.
As weird as it is to hear, Xenosaga does that for me, as does Shin Megami Tensei (IMO, the king of balanced story and gameplay).
Shin Megami Tensei is firmly in the gameplay first category. For every minute of story you get in a Megaten game, you're guaranteed at least a couple hours worth of gameplay. Admittedly, what story you do get is really good, but the story is mostly just a bonus added on to the gameplay experience.
Planescape is indeed one of the few RPGs with a truly great story. Unfortunately, I can't stand the combat (I hate all the randomness involved in D&D style games). Otherwise, it's a great game.
just wanted to add that if you try to button mash on the higher difficulties of ToS you will fail horribly
also reading this thread got me to thinking that a "Eternal Darkness" style rpg would be awesome. and by this im not referring to the theme of the game but how the game plays out through generations. with most of the characters playing small roles in the greater struggle.