I can add a few comments from my trip to the area.
You may already know about it but be sure you also see Hohenschwangau at the same time (you can get a combo ticket). I have some friends who went to Neuschwanstein as part of a bus based tour and they did not go to Hohenschwangau due to time. When I went I had my own car, so we set the schedule. It does not take much longer to see it (it is just not as famous). At Neuschwanstein be sure you walk the path up to Marienbrucke (rainbow bridge) to see the other side (hopefully the scaffolding is gone by the time you go, it was basically covered in October 2009). Before you leave the Fussen, I think taking a trip on the Tegelberg is worth it. You get a great view of the front of Neuschwanstein but you also a wonderful view of the who area from the top of the mountain. When we were there we also saw hang-gliders and para-gliders launching from here, really cool.
I am sure you know about it already, but be sure you take the night watchman's tour. Rothenburg is a lot like Neuschwanstein in that it is very touristy but if you expect that going in, it is fine.
I also did the Eagle's Nest and Salzburg, both are recommended.
The only other place we went that is near your current plan is Munich. Munich will have more things that may interest your wife (compared to Rothenburg and Fussen) but also many things you may find interesting (palaces, museums, monuments, etc.).
We rented a car when in Germany (though not when we were staying in Munich). I would think having a car would make it a lot easier getting to many of the castles that are not in big cities. Obviously it is easy to get around inside the cities using public transportation and the trains between cities are great. If trains go to the castles you want to see, by all means go for it but driving in Germany is really easy (well we had a GPS). The signs are clear and the roads are great. When going between the cities you will find sections of the autobahn that still no speed limit and I kept the rental car at top speed (though it could really only do much over 150 kph going downhill). If you do drive, keep in mind the left lane is for passing only. You pass the car/cars in front of you and then get back over, otherwise you will quickly have a big, fast BMW/Audi/Mercedes on your bumper flashing their lights before you can blink.