I am looking for a service that will give me SSH access to some sort of Linux server (even if it's in a virtual machine type thing) that I can use to run my Minecraft server. It needs to be:

-less than US$25 a month
-have fast connection speeds
-have the most RAM I can get for my money
-have Linux

It does not:

-Need to come with a website domain name (so long as the server's IP address won't change randomly)
-Need to have any apache/web-page-hosting stuff pre-installed.

And which country would you like to receive this service in?
There are many hosters out there, even low budget ones - however i am uncertain if such a low budget virtual server will give you the amount of cpu time you desire.
server4you.com could be an option for you depending on where you seek these services to be located, i.e. there is no use for you to get a server in the US if you are located in DE as i'd assume your latency to be quite annoying ;-)

Its in the U.S., and RAM is actually more important than CPU

providers of virtual private servers often split cpu time amongst the various virtual machines or containers. This does not limit the amount of frequency but the amount oc calculations available to your container / VM.
Depending on the style of game this can be a significant issue.

Perhaps you want to look out for a provider who allows cancelling the contract on a monthly basis, this would allow you to run a test without being stuck with something you cannot use for whatever reason.

Else you can look out for game servers - they will merely provide you with access via ftp and a web based control panel to configure the game you are 'renting'.

You might have a look at Linode.com They offer a virtual server package for about $20/month in a variety of Linux flavours. ASamallOrange.com also has a low prived VPS package in your price range. Both are reliable, quality services.

thx everyone. I'll look at those sites.