Guides: I use guides very selectively, and rarely find them via hotels, more often thru other commercial enterprise, and often they find me and I size them up on the spot. Unless I have a first-hand recommendation from somebody I trust, I always limit an "unknown" guide to at most one-half or one day, to see if I like or not, and to give myself an exit position. If I like them and need services for another day, I hire them again. Don't underestimate your own abilities, or overestimate what guides can do for you. For specific places you've mentioned:

Jakarta--no guide needed. There are two main places of tourist interest in the central city: the Merdeka Square/National Museum/Mosque area and the old Dutch Kota area. A taxi or the local bus can get you to these places, and reading a guidebook and a map will do you fine.
Surabaya--ditto. I thought the House of Sampoerna Museum and free bus tour was great, and also visited the Zoo. I think you'd only need a driver/guide if you wanted to go further afield to Madura Island or similar.
Jogya--ditto. Most things of tourist interest excluding Borobudur and Prambanan are in a small area of the central city, partly walkable and partly by becak is best. Some places, like the Kraton (Sultan's Palace), have the option of guides for that location--which I took a pass on in favor of reading my guidebook. At Borobudur and Prambanan you can hire site-specific guides at the entry/ticket area--but I'm well versed in SE Asian architecture and monuments, and with a good guidebook, I didn't feel the need...
Medan I don't know but it has the reputation of being a dump of a city with nothing to see, but a necessary transit evil for those heading to Danau Toba or Gunung Leuser areas. Guides for those areas are best picked up once you get to those areas (so I've heard), but I'm sure you could have private travel + guide arranged in Medan.

Bali: (from a past trip about 3 years ago). A guide, or driver that speaks enough English, is pretty much needed here, as much of interest is widely scattered around the island. I stayed in two places: Ubud, where drivers mill about the main streets daily, looking for business--we just negotiated a day rate with somebody we had positive vibes about, and told him the itinerary we wanted for the day. What was great about this guy was not the standard "sites" spiel--which the driver didn't really have--but the great color commentary he provided about life in Bali, current affairs/issues of the island, etc. There are also plenty of small agencies you can walk in and make arrangements for whatever you want. We did a day of rafting/nature stuff and booked with an agency in Ubud for that. The second place I stayed was an isolated area in the far north of Bali, and for that we arranged with the guesthouse for driver and guide, for a very long day trip that covered much of the eastern half of the island. And also for a separate 1/2 day trip to Singharaja area. Some important places of interest have "official" guides you can hire on (or get strong-armed into it--Pura Besakih was fairly aggressive about this but other places were not).

Hotels: on the Feb 2010 trip, my budget was in the US$40-50 range per night, as I needed simplicity, privacy, cleanliness and a/c but not lots of business or luxury amenities. I didn't want to do the rock bottom backpacker thing on this trip. I also like staying in central locations for transportation purposes (don't like isolation when travelling alone). I found myself staying in a lot of Accor hotels, which isn't typical for me but worked well this time. Before travelling, I prearranged the following, and ended up happy with my choices for this price range (remember Feb is low season in Indo, prices may be somewhat higher at other times):
Jogya + Borobudur: 1 night Phoenix Hotel (colonial, historic, nice), 1 night Manohara Hotel at Borobudur (staying here, you get reduced admission for the sunrise tour 175,000 Rph instead of 350,000 Rph, and free admission at all other times of day as much as you want), 2 nights Ibis Malioboro Hotel (clean and great location).
Jakarta: 2 nights Ibis Arcadia Hotel (also clean and fabulous location).
Surabaya: didn't prearrange, just got off the train and had a taxi take me to the Mercure Hotel, gambling they had room and a decent walk-inrate (they did), 2 nights.

Bali: (previous year's trip, and more expensive about $100 per night for February, but that trip had a different purpose and budget ) Ubud: Kajane Mua on Monkey Forest Road. Sambireteng (far north-northeast coast): Villas Agung Bali Nirwana. For a place like Bali, I'm not a fan of the international chain hotels or their locations like Nusa Dua and Jimbaran--prefer guesthouses and villas--and not a fan of the raucous party crowd at Kuta. Bali has something for everybody though, and it's horses for courses as to preferred location and accommodation.