Most restaurants mentioned on this thread serve the best Indonesian food in a restaurant setting. Of course there are cheaper ones as well, but generally the food will not be as special.
Affordable Indonesian food is to be had at so called toko's, which are usually a take away option though might have one or two tables. Usually they will heat it up for you if you don't have facilities where you stay. They will also sell Indonesian ingredients and sweets. This is where many Dutch families get their Indonesian food fix.