Order does matter.
Sadly, it's hard to tell exactly how it will matter in your situation. If you can, make a dev copy of this site and experiment on it. I would either go with core-first or with all at once. But that's my intuition, and actual tests on a copy of actual site matters much more.
Usually it's OK to jump all versions in-between the one you have and most recent one. For modules, sometimes, rarely, it's good to use most-recent minor version and don't install next major version at all (if both are maintained), or install most-recent minor and then update major. Sadly, it's different for each module, so fastest thing would be to update everything straight to the recent version, and see if / what broke. Of course, this is only feasible on a dev copy, not production.