lowendbox is always a good starting point for cheap deals.
https://lowendbox.com/
You can get away with really low specs but you must have a swap file if you're compiling yourself. I wouldn't go with anything less than 10GB storage.
I personally pay about $4pm to OVH because I like their management console.
I believe ArubaCloud is even cheaper, but they require a copy of your ID which is a NO GO for me. If you don't mind, check them out - ArubaCloud: www.arubacloud.com (starts at € 1,00 p/month)
Also be careful while sining up on Arubacloud. Check the URL which you are about to sign up thru. If it's "cloud.it" the cheapest price will be 4.99 not 1.00. Make sure you sign up thru "arubacloud.com". If you will be redirected to cloud.it over and over again ask their support to provide you the sign up link to arubacloud.com.
Also I have noticed that their support is pretty strange... they dont answer direct questions and act a fool like:
Question: I cant find the 1.00 € plan in my account the cheapest is 4.99 € whats wrong here?
Answer: If you want to create a VPS in your account go to blah blah...
But it's not the answer to my question... I guess you understand what I mean.
I also made the mistake and signed up thru cloud.it I asked them to delete my account so that I can sign up again thru arubacloud.com. it's like two weeks ago and my account is still not deleted... so be cateful with them.