Xenoblade is exceptional.

Strange thread, if you want magic on the ds platform in terms of story go for professor Layton, not jrpgs but obviously if you wanted a machine for those you would have gotten a vita, regardless of it having less western support now this doesn't change the fact that the machine has games directly from the ps 3 like disgaea 3/4 complete with all their dlc or even jrpgs that are only on that or the ps 4 like the amazing digimon Cyber Sleuth

Oh also buy ghost trick, rhythm heaven and theatrythm final fantasy. All amazing games, do not Google ghost trick, just buy it and play it, you won't be disappointed 

Get Dragon Quest 7 or if you hate cheesy, get Shin Megami Tensei 4 and Apocolypse

Well, for story I'd recommend the Professor Layton games as well as the Ace Attorney series. You can get the first three AA games on the eshop pretty cheap and the 3DS is DS backwards compatible so you can just pick up the entire Layton series used if you want to.

None of those is a jrpg though, Layton is a puzzler and AA are visual novels with point n' click elements.

People have been recommending Xenoblade Chronicles and I can second that it's an amazing game.
Also you bought the pokemon machine. How about some some Pokemon then? There will be six games to choose from shortly.

If you like Fire Emblems gameplay, but not the story, maybe try out Awakening. I hear the story is better.

Although I have to say, if you don't like cheesy drama jrpg might just not be the genre for you.

You thought Fire Emblem had boring gameplay? That's the best part of fates altogether.

i'm sorry, I have to conclude that you have very poor taste after spending most of your life with shooters on Xbox platforms. There's no hope for you, and you've also completely dismissed the Vita library as well. Stick to your Xbox. 

Shin Megami Tensei IV & Apocalypse. Fire Emblem Awakening is better. Dragon Quest VII.

Funny how you play 2 series and get mad lol

Monster hunter and Fire emblem is nothing compared to nintendo's legendary franchises. Try kid icarus uprising, Mario 3d land, ocarina of time and majora's mask 3d, etc

The 2 games you got are some of the biggest commitments a 3DS owner can make of their time.

I'd invite you to take up more casual, pick-up and play experiences for your 3DS. Stuff you don't play for story, but for the sheer joy of wasting 5-30 minutes when your waiting in line somewhere, while your wife/gf watches something stupid on TV, and other random downtime. 

The 2 games I most highly recommend on 3DS would be A Link Between Worlds and Super Mario 3D Land. Common answers - but they're paced beautifully well for either casual or long-form play. If you don't plan to get the Switch soon, I'd recommend also getting Smash too. Smash is so easy to pick up, but is so satisfyingly deep too. MK7 gets a similar recommendation.

If you like retro games, the Sega 3D classics are great too. Especially Streets of Rage 2.

I can't be as helpful for your RPG needs though. But I have little doubt you'll like Xenoblade - but again that game is also a big commitment. SMTIV, Bravely Default/Second, and Dragon Quest are the marquee turn-based RPGS outside of Pokemon.

If you want a great game that's shorter with a solid story - you really need to look at Ocarina of Time and Majora's Mask. If you never tried them, you owe it to yourself to see what the hype is about.

I realize this is a very 1st party centric list - but honestly you seldom go terribly wrong with Nintendo 1st party on a long term basis.

I don't know exactly what are your tastes, but FE:Fates is arguably the best SRPG game out there. If you don't like it stay away of those games. There are a lot of good RPGs on the 3DS. Try SMT games, they're really good. The 3DS has lots of critically acclaimed games, just make sure you like the genre.

Well yeah. If you want a good fire emblem with great characters/story/etc, don't buy Fe on 3ds/ds.

Path of Radiance and Radiant dawn are the best of all Fe, with FE4.

FE fates was pretty boring for me. And not only for the characters and the story, but the gameplay too.

If he don't like Fe fates, he will SURELY NOT like Bravery too much default.

Not a good advice at all, sorry.

The only game close to what the author want is probably SMT4, and maybe others Atlus games such as Devil survivor 1.