If there's something this game could really use, its some sort of fast travel.
Kinda like in xenoblade chronicles, let the party warp to places they've already been. Takes out a lot of the walking time.
That said, boss ideas:
any legendary pokemon of the appropriate type
deadbeard/dullahan from golden sun
crystal king from paper mario
Btw, will the elemental shields (or any equipment, really) eventually be sold? I missed one or two and its kinda hard to find the missing ones.