Scenic stop for one night between Fussen & Basel by train

Lindau is about halfway. Stay on the island. You can get there with a Bayern Ticket.

You could continue to Basel by taking the ferry across the lake to Rorschach, then train to Basel from there.

I agree. Lindau is the place.

The Baden-Württemberg Ticket gets you from Lindau to the Basel-Bad station in Germany. Transfer to local transport there for Basel.
Railway Map: http://www.agilis.de/wp-content/uploads/2016/11/Streckenkarte-BW-2013.jpg

Bayern Ticket and B-W Ticket info: https://www.bahn.com/en/offers/regional/regional-day-tickets

Another vote for Lindau. In 2013, my partner and I were travelling between Sigmaringen and the Allgäu via Friedrichshafen and Lindau, along the lake. When we changed trains in the station on the island, we could have just stayed on the platforms, but I wanted her to see the harbor. So we went outside of the station and one lock at the harbor, and she feel in love with the town.

In 2017, on our last trip to Germany, we had to spend more time (4 nights) on the island. On our second day we took a ship across the lake to Rorschach, Switzerland, and came back by train around the eastern edge of the lake through St Margrethen and Bregenz, Austria.

Another vote for Lindau. It was my starting point and ending point for my 2006 biking adventure around the Bodensee (Lake Constance). The harbor area is beautiful and I enjoyed watching a really fun street entertainer. Great photo ops, too.

not to pile on but I like Lindau too

I like the idea that Sam suggested, taking a ferry from Lindau to Rorschach. We will be traveling in March. Would it be too cold for a boat ride?

I don't believe the ferry runs in March. The way through Germany suggested looks like the best way. Although Lindau is in Bavaria, the Baden-Wuerttemberg website indicates that it is valid to use a B-W Ticket to get to Basel Bad station. It is a direct IRE train from Lindau Reutin to Basel Bad bf., taking about 3 hours. Lindau Reutin is just a short train or bus ride from Lindau Insel.

I don't believe the ferry runs in March.

Alternatively, the ships from Friedrichshafen to Romanshorn and to Konstanz run all the year round, and also from there you can get by train to basel.

I don't believe the ferry runs in March

According to the schedule I could find, the Lindau to Rorschach ship started running on May 18 of this year.

According to the Bahn website, it runs every day until Sept 10, 2023, then mostly only on weekends until Oct 15, 2023 when it stops running. It does run on Monday, Oct. 3 (day of German Unity, also the last day of Octoberfest).

Also on the DB website, it started running only on weekends Apr 2 and started all week service on May 18, 2023. It also ran on the 7th and 10th of April (weekdays).

If you just want to go to the Swiss side of the lake, there is a large car/passenger ferry from Friedrichshafen to Romanshorn that runs almost daily during the winter. For 2023, the schedule on the Bahn says "runs daily, not 12., 19., 26. Nov, 3. Dec".

In 1988, I started in the Allgäu (Immenstadt) and came down on the train to Lindau, then went along the lake to Friedrichshafen (Zeppelin museum), took the ferry across the lake to Romanshorn, the train to Kreuzlingen, and went across the border back into Germany at Konstanz. From Konstanz we stayed in Germany and went through Donaueschingen and Titisee to Freiburg, but we just as well could have gone to Basel on the German side.

As mentioned above, a Baden-Württemburg pass would cover your travel through German (not going to the south (Swiss) side of the lake), all the way to Basel Bad Bhf. However, between Bietingen and Erzingen you would have to travel through Schaffhausen (Switzerland) and you would need a Swiss Rail ticket (looks like 6,70 CHF) in addition to the Baden-Württemberg-Ticket for that part of the trip. You could also travel on the German side through Donaueschingen, Titisee, and Freiberg entirely on Ba-Wü-Ticket but that would add several hours to you trip.

And, of course, you could do as other have suggested, cross over on the ferry from Friedrichshafen to Romanshorn and then go by train via Zürich to Basel on Swiss Rail.

I've never gone through Schaffhausen, but I hear it is scenic. I think if I were doing it, I'd go from Lindau to Basel by way of Schaffhausen and buy the Swiss Rail ticket for the part from Bietingen to Erzingen.

However, between Bietingen and Erzingen you would have to travel through Schaffhausen (Switzerland) and you would need a Swiss Rail ticket (looks like 6,70 CHF) in addition to the Baden-Württemberg-Ticket for that part of the trip

The B-W route map shown a this website clearly shows that no additional Swiss ticket is required for the short-cut through Schaffhausen, Switzerland.
https://www.bwegt.de/tickets-angebote/tickets-im-bwtarif/baden-wuerttemberg-ticket

Also contains this statement (using google translate).

NEW: The Baden-Württemberg ticket is now valid to Lindau-Reutin. The extended area of ​​validity is not yet shown in the bwtarif route map.

The map shows "Lindau Hbf", which has been renamed Lindau Insel. The IRE train to Basel Bad bf starts in Lindau Reutin, so you have to take the short connector train from Lindau Insel.

Sam, thanks for finding the B-W Streckenkarte for me. I spent a lot of time looking for it on the bwegt website today. So, it looks like you can go from Lindau to Basel using just the Ba-Wü-Ticket. I already knew Lindau to the Ba-Wü border was included in the ticket.

Seems if you leave from Reutin, there is, as you said, an IRE all the way to Basel, but if you want to leave from Insel, you can take an IRE to Friedrichshafen and change there to the IRE from Reutin. There are also three trains and a bus from Insel to Reutin every hour. Or you can just walk, it's not that far.

Strange. If, using the Bahn website, you put in Friedrichshafen to Basel, it will show the IRE and the Ba-Wü-Ticket. Even it you put in Langenargen (the first stop in Ba-Wü coming from Lindau to Basel, it will show the IRE with a Ba-Wü-Ticket, or even if you put in Nonnenhorn (in Bavaria) it will show the Ba-Wü-Ticket, but if you put in Lindau to Basel, it won't show the Ba-Wü-Ticket. Huh? Must be a programming error.

Lindau is about halfway. Stay on the island. You can get there with a Bayern Ticket.

A Bayern-Ticket for two is 36€. You can also go from Füssen to Lindau-Insel for 33€ with a Regio-Ticket Allgäu-Schwaben. It's only 3€ less, but why not?

I noticed that as well. But the B-W map of validity is pretty clear.