Ya, I hear ya. I'll tell ya what I do...but it is for windows.
I use Winamp on the PC and I use aWARemote. I found it to be one of the best interfaces out there and offers the best controls. Pretty cheap too.
aWARemote Pro for Winamp® - Android app on AppBrain
I know you don't wanna hear this...but when it comes to finding apps like this, your choices become pretty limited by Linux. gMote was the only app I found that allows remote control and Linux support. I think you saw that one too....it is not ideal for your purposes.