Brian,
I previously worked for AllGamer.net. They are good for the cost. ($15
a month for 512mb) I agree the server software is a pain, and it takes
a lot of getting used to. Regardless of who you pick though, if they
want a modded server you will be playing PluginCraft(uploading plugins
and configuring them via yaml files) whilst they play minecraft.
That said if you want to just run one at home, there is a control
panel that works really well and runs on linux/osx/windows called
McMyAdmin. It takes most of the pain out of setting it up. The
personal version is free, but limits the server to 8 players.
AllGamer is on IRC at
irc.rawrirc.net #allgamer and McMyAdmin is on
irc.esper.net #mcmyadmin
Sent from my iPhone