I just spent something like 4 hours changing the default...
...using this base stylesheet (don't miss pull requests #1 and #2 if you do the same), fetching certain snippets of code (all those related to color/background) from this custom skin made before WP had native ME support, cutting out an alignment bug in the vertical volume slider thing by changing the top:-21 to top:-11 somewhere in the code (you'll figure it out), and a few site-suitable margin and alignment adjustments later... it's not looking all that bad!
The documentation for MediaElement.js in regards to WP seems to be pretty much non-existent, and it took me quite a bit of research to finally figure out how to even change the width on these new shortcodes - much less do anything wild like adding rounded borders and different colors. This mostly because all styles and scripts related to ME are hidden within wp-includes, there's no official documentation, and the original code (at least the stylesheet) isn't at all structured with modding in mind.
I found a few pages advertising workarounds such as very specific CSS rules or using
!important to override certain rules, but the best option is clearly to first dequeue the 'official' core-included MediaElement stylesheet (via your theme's functions.php), copy this stylesheet to your theme folder where it can be modified, and then include this CSS again either via a link in functions.php, via @import, or directly into your main .css file. I'm assuming one of the latter two options would cut down on requests while loading site resources... personally I settled for @import. The only caveat with this technique is that any updates to the core file, you'll have to make manually.
How to dequeue the official stylesheet is mentioned in the Read Me! for that basic stylesheet, and you can use the same method for any other parts of the ME library, like the JS files. There's some useful info on such files here, along with info on custom event handlers, etc.
Also, if you want playlists with download links, see this. And if you want playlists in the first place, there's this plugin. Hopefully this post will serve as useful reference for others than myself! You can see a live version of the custom player here.