Maybe I will have the unpopular opinion here... but I have never worked with an Implementation partner... and I am not sure if I would recommend that or not...
If you are comfortable implementing analytics (not necessarily AA, but other analytics programs) you should already have a base understanding that you can build on.
Adobe has instructor led training courses (https://learning.adobe.com/catalog.html) that you probably should consider taking one or more of these to understand the specifics of Adobe Analytics, and those will cost far less than a Partner. (The "Adobe Analytics Implementation" course would probably be one of the better places to start).
If you have a simple implementation in GA currently (from the sounds of it you do), a simple implementation in Adobe is pretty easy, and as you gain confidence in the system you will learn and grow into it. Not to mention there are tonnes of learning resources available from Experience Leagues, Adobe's YouTube channel, Adobe Analytics User Groups (https://analytics-augs.adobe.com/chapters/), and more. An implementation partner may be able to help you get going on more advanced things sooner, but if you are pro-active, you can learn these things from the wide community around you.
The other option is to hire an independent consultant (basically someone with a lot of experience implementing Adobe Analytics under a short term contract, with the potential to extend) who would be a part of your team for the duration of getting up and running.
Anyway, that is my 2 cents on the matter... but it might be coloured by the fact that a few months ago our company was thinking about buying Google 360 (on top of Adobe Analytics - I really don't know why), and the "partner" was mandatory... so basically we would have handed over a tonne of money for them to basically do nothing (since we already know how to implement GA and already use the free version as our backup analytics).