@Darkstorm:
Flame of Recca, while fantastic doesn't really have that "adventure" feel to it.
Hunter X Hunter.
But Hunter x Hunter is lacking a big amount of fanservice. And the last arc had the tendency to be more fighting than adventuring.
Same goes for Shaman King and D-Grayman which started good and became just the next replacable DBZ Clone.
Psyren has the tendency to be adventurelike but in a postapocalyptic world and it didn't reached the point and hopefully will never where it's only the fighting that counts. But it's way more serious than fairy tale.
One Piece is the King when it comes to adventure and worldbuilding, but you wouldn't be on this site if you not already knew.
Not clearly what you are looking for but they have quiete a share of adventure and fanservice:
Claymore (Serious Shonen, dark worldbuilding, because most protagonist are women you get a share of fanservice)
Berserk (very dark seinen, very grim but insanly rich world, brilliant drawing, fanservice included but like i said much more depressing and grim than fairy tale)
Deadmans Wonderland (Dark seinen, but if you are into black humor,it could be your thing, lots of fansercie, crazy sadistic world)
The last three, like i said, are eventually not what you are looking for but have similarities. So maybe you will like them.
Edit: Tenjo Tenge (The King of Fanservice, and a good seinen fighting manga, but you will most likly miss the adventureparts)