|Perl Monk, Perl Meditation|
To respond to just some of your points:
useful to someone who lives in US west
IME, so long as they invoice in my currency and are responsive during my hours of business it doesn't matter too much where they are so you might consider casting the net a little wider. Exceptions are for jurisdictional matters (GDPR, etc ad nauseam)
allows me to have a *nix system with sudo privileges
Any hoster offering a VM/VPS/Cloud Server these days will give you this. Expect to pay the equivalent of 5 to 10 GBP per month for an entry-level VM.
will finally let me install Mojolicious
doesn't assume that I'm some huge business: I'm not
This one can cut both ways. I am generally happiest dealing with smaller providers (simpler APIs, panels, etc. and more often a more personal approach) so I know what you mean. Just make sure you have an exit strategy - anyone can go bust with almost no warning, even the big beasts.
That bit about being one of the few places without smoke has certainly changed, and I am stuck inside.
Stay safe, brother.