There is nothing grammatically wrong with either of your examples. I find that the phrasing of (a) lends itself much better to the poetic nature of the context.
I agree. (a) is in fact a case of full inversion. Similar examples can be found with other adverbs in front position, like first, then, here, there, out, in, off, away, etc.
I think there should be a comma after Next in (b). Otherwise, this might sound better and more balanced:
(c) The graceful palm tree came next
which reflects the "normal" order of sentences: Subject - Verb - Objects - Adverbials