Well, i’m not 100% sure, but i think this should work either way (upgrading Openfire to 3.9.1 first and then Spark to 2.6.3 or latest 2.7.0 builds, or vice versa). There certainly were a lot of changes in the Openfire and Spark code, but they are still xmpp server and client working by xmpp standards, so basic features should work the same. There could be some compatibility issues with file transfers or voice chat between Spark 2.6.0 and 2.6.3 or 2.7.0.
That being said, upgrade from pretty old 3.6.4 to 3.9.1 can be not very smooth (in theory it should be ok, but sometimes such version jump gets complicated while updating the database structure). You should make backup of your server before upgrading. Also try upgrading a few clients first, to see if all works as intended.