Music on Apple Watch without iPhone
MixTape turns out to be an excellent solution that costs only $3.

http://dorshorst.com/mixtape/

I'm not sure what changed between now and Feb 5th when I first tried it (and commented above) when literally nothing worked but I tried it again today and it worked perfectly for my needs. 

As pointed out by @dwightk, Pandora as of 2019 does not support streaming directly to the watch, but does allow you to manually transfer songs to the watch for offline, phone-free listening if you are a Premium subscriber.

So far those are the only two solutions I can find.