I would love a wind waker inspired great ea expansion. You grab a little ship mount or a big guild galleon and set sail in a huge sandbox ocean with each zone being an island. Sometimes its a jungle lost world deal. Others its just being settled by the alliance and horde civilians for farmland and they dig something weird up or a crate of old plagued grain washes up on shore or something.
Add into that vash'jir style sea floor stuff with ancient ruins and treasure maps and sea beasts and guild vs guild ship battles and maybe some skies of arcadia style exploration and discovery rewards and you would have an expansion i would flip my wig for.
and a voodoo-ey meets swashbuckler piratey class, of course.