I know this information is out there but I guess I'm not searching for it Correctly:
I'm looking for an example using a python script to publish a map service using an .mxd file.
You might want to look at the ArcGIS Server Administrator toolkit
...tools for starting and stopping services, modifying log settings, registering server object extensions (SOEs), and publishing services from service definition files.
(The tools are a starting point, although you may need to update for your purposes. For example, I have modified some of the scripts to do things like find running services that use datasource X.gdb then stop those services, replace the fgdb, then start just those back up (instead of trying to remember which you stopped). There is a never beta version of those tools..but I don't have the link handy.)
Also check out
and some of the related links to get started.
An old question on Geonet:
Which leads to this blog post (last comment suggests code -on GitHub- can be made to work with 10.5):