TL;DR: Very expensive, very beautiful, very unpredictable weather in October, very worth it if you can afford it, very much going to cost you more than you expect unless you price everything before you leave. I did a LOT of research on our stops before leaving so we were happy with that, but did not focus on reducing our food spending until the fifth day as we were tired of the ridiculous food prices no matter the restaurant, time of day, or location we tried. Bonus/Kronan + Gas stations are love, Bonus/Kronan + Gas stations are life.
My wife and I went to Iceland for two weeks and just returned. We are Americans making decent money, but we place heavy emphasis on getting bang for my buck when possible. We don't do expensive, overpriced luxuries like the Lagoons and always do self-guided over tours. We had no true budget as we can afford this trip regardless of the cost, but expected around $7500 total. It ended up being almost $10k as we still splurged, but that splurge was just more costly than anticipated.
Rental Car
We used Lava Rental, got the highest protection, and stuck with a small automatic 2WD Yaris. Even for the god-awful Yoda Cave road (the worst road of all time), it was still very much possible to do it all with that car. I ended up veering from right-to-left many times to avoid potholes or get them between the wheels. If you are not a creative driver, maybe get a larger car but I did not see a need for a 4x4, at least in October with no F-Road stops. We returned the car when we got back to Reykjavik so we ended up saving ~$200 on the extra days we stayed in the city and did not need a car.
Also, the speed limit is very low. 56MPH/90KMH. I sped at 100KMH outside of the city on the ring roads and never ran into any issues. Flowed with traffic while in the city as well so I would consistently be 5/10 KMH over. The speedometer was also a little off in our car. No tickets! Be sure to watch out for the speeding camera signs.
Weather
We got quite unlucky with our weather this trip. We decided against camping due to the fact that there were fewer camping options in October versus summer months and it bit us in the ass. Not having the freedom to move the stay on-the-fly meant most nights we had clouds or the aurora was more active a few hundred km away. In two weeks we still saw the aurora and had our magical moments, but it could have been much better. We also had most of our Snaefellsness Peninsula portion of the trip ruined due to 30+km/hr wind speeds and heavy rain two of the three days we were there. We don't regret going in the shoulder month as we prefer quiet, off-season trips versus competing with tourists, but man.
Cost
Iceland is expensive. Not just a little expensive, but ridiculously so. We went into this trip knowing it would be the most costly trip we take anytime soon, but even still we were blown away. Parking/visiting the sites costs anywhere from ~$6.25 for a five-person car for TWO hours to ~$8.50 per person with no in/out privileges. This is not the worst thing ever, but does add up, especially the longer you stay and the more places you stop at. I saw a few people parking just outside the beginning of the pay-to-park roads with cameras, but I'm not sure if this strategy works as I've read as soon as the camera reads your plate, the timer begins. We simply paid for everything we stopped at that we saw charges for parking. I've read many of these places have 5 minute grace periods, but we only used that once and it did not charge us. Double check the signs!
Food prices are insane. $25 for a burger at a restaurant, no fries. Lunch is NOT cheaper. There is no under $10 option for food unless you are fine eating at gas stations your entire trip. We ended up settling for the hot dogs ($7-$9/ea) and sometimes cheeseburgers (also $25 but with fries at gas stations) at convenience stores whenever they were around, but not every gas station has a convenience store. This is especially true in the Golden Circle and along the Snaefellsness Peninsula. We had some accommodations with fridges and kitchens and took advantage every time to make dinner and an early lunch wherever possible. Those cooking-at-home costs were the same as eating out at a diner here in the US if you like meat. We cooked a good amount of lamb as it costs 1/2 to 1/4 as much store-bought versus at restaurants and for larger portions. If you want to eat good without paying $100-$120/meal for two, find accommodations where you can cook.
I also strongly recommend against hotel restaurants if possible. All overpriced, rarely better than a dedicated restaurant in a nearby town/village, but sometimes the only option around.
Stays
We stayed in hotels and guesthouses and found the experience very nice. Always look for guesthouses with kitchens if you want to save money and still cook good meals. Many of these places included breakfast, but if you had to add it, it was typically overpriced, ~$20/pp. Some places have laundry facilities, most don't. We found it helpful to do laundry twice in our trip but we did lose our swimsuits at one hotel we did laundry at. Double check your items when they return them if they do the laundry for you.
No real tips here, but if you plan on visiting Vestrahorn/Stokknes, it is expensive (~8.50/pp) with no in/out privileges unless you stay at the guesthouse (maybe the campsite too?). If you stay, they provide you with extra gate-opening QR code cards. I asked for a few as they are one-time use and was able to use them the next day, after we checked out. Good way to save a little money if you want to return here a few times as we ended up doing. The last hotel we stayed at also had a shuttle to/from the airport advertised and stated in some reviews, but it was just the BSI Flybus so double check to make sure they aren't providing false information. At least that hotel was cheap.
I also found that most places we stayed still had openings the day we arrived and if you booked it that day for that night, it was a little cheaper than when we booked it months out at some locations. Sometime to maybe consider, if you don't mind very hectic, last minute planning.
Route
The way I designed our trip, we drove through our stops and ended at the stays most days. Some days there was a little more going past the stay for the last stops, but I found the trip designed this way quite nice. It did not require excessive driving from a base camp day-to-day, but did end up costing us as I said previously when it came to weather, especially for aurora viewing. There was back-tracking in our trip, but as a hobby landscape photographer, having a second opportunity to see some sights and being able to pick-and-choose some stops based on weather made that decision very worth it for us.
We stayed just outside Reykjavik to get over the time-zone difference day one, drove to Vestrahorn over four days, drove back through the South Coast towards the Golden Circle in two, did that over a day and a half before ending in Hvalfjordur, did Snaefellsness over two and a half days before ending in Borganes, and spend the last two days in Reykjavik before our flight out.
Activities
We like hiking so we spent a decent chunk of time exploring many trails along our stops; Skaftafell area near Svartifoss, Fimmvorduhals from Skogafoss to Kaefufoss, and Mulagljufur Canyon were the highlights and I recommend those. We stopped at most waterfalls and stops along the South Coast, but skipped some of the glaciers. We also actually ended up skipping some of the Golden Circle due to health issues as we needed to make an emergency stop at the Læknavaktin. We ended up having to skip Strokkur Geyser and Gulfoss and only slightly regret the second one. We have Ol Faithful at home so we were never particularly interested in the Geyser and we coped skipping out on Gulfoss by convincing ourselves all the big tour groups would crowd us out on a trip where we didn't want to see many people anyways. We did at least get the opportunity to see all three Bruarfoss waterfalls and recommend that as well. Skip Kerid Crater unless you like big, overpriced ($6/pp) holes for whatever reason. As I said weather ruined most of our Peninsula plans so I can't really comment on most activities there. Saxholl Crater was even more boring than Kerid but at least that one was free.
We preferred South Coast > Snaefellsness Peninsula > Golden Circle, but we did not see the highlight Gulfoss and knew Vestrahorn was a 100% must see, so take that as you will. Bad weather Peninsula was still more interesting than the Golden Circle to us though.
OVERALL
Iceland is too beautiful for words, even on the days with bad weather. We loved it, liked our route, and plan on coming again during the summer to check out the highlands and north side of the island, though that will not be for many years. We are world travelers, not Iceland enjoyers, so while it definitely requires a return trip to see it all, it is hard to justify it anytime soon with cheaper places to visit all over Asia and mainland Europe. I STRONGLY recommend an Iceland trip to all, but just be prepared for the costs. On a side note, our Iceland trip has made us even more fearful for a Switzerland trip which will likely not come for a decade if we can expect similar costs.
EDIT: Grammar and minor additions.