Which to Upgrade first? My Amplifier or Speakers?

Nothing. 

It's only an "upgrade" if you have a direction you want to go in.  Otherwise it's just a change.

What do you know you like better?  Anything? 

I'd wait until you're in your new home. With more flexibility in speaker/listening position and the ability to add some aesthetically appealing room treatment, you may be satisfied with what you already have. You would need two subwoofers, not one for proper music reproduction. Trying to get ideal home theatre (articulation of speech) and stereo music reproduction out of one system is always a futile exercise.

If I was in your position and did want to change speakers, amp or both and considering this is a pro audio forum, do what many of the best recording studios in the world do and go with active ATC speakers within your budget.

I knew a professional musician who had a very good Magnapan system in a nice, purpose built, dedicated stereo listening room switch to active ATC speakers.

Finally, regarding fine tuning of your existing components, I strongly recommend getting Jim Smith's $35 book, Get Better Sound. Follow his advice in your new home and you may not need to upgrade anything.

Get Better Sound

Agreed with the many others that suggest trying other tings first, given the quality of amp and speakers.

I particularly like the suggestion of subs, given you can't really do room stuff.  I'm definitely not a wire skeptic, but I bet subs would make a more noticeable difference, bottom to top, than wires, even if your wires are very modest.

But I totally get just wanting a change, certainly a valid reason in this hobby.  If that's it, like others, I think speakers is the way to go.  That said, I've shopped a lot at that price point, and my experience is there are lots of excellent choices, but few that stand out from the other excellent choice..  So shop, go to shows, have fun, and maybe you keep your Maggies.

Surely the speakers as they make more of a difference to the sound. you can then get an amp that is matched to those speakers.

The first frequency to drop out with volume is bass response.  Consider buying 2 REL SHO’s.  They will create a wider sound stag.  They will also allow you to hear bass at lower volumes.  REL’s high level connection also helps the subwoofers to play like woofers.  The volume needs to be about 40% and the crossovers set at right frequencies.  I think most people play subs way to loud.  This is also why playing two is better than one.  Pushing air more evenly and balanced really improves sound.  I am not a big fan of Maggie’s.  I hope you listened to other speakers as well.  It is all about what sounds best to you.  Good tweeters can also bring out more detail.  Most of us also have hearing loss in higher frequencies.

there are really knowledgeable people in this group.  A great place to get ideas.