The house of bourbon would look like weak rulers who had sold france to foreign powers and wouldn't care what happened to france as long as they ruled .
I'm not sure whether that was really that much of an issue - particularly after the 100 days. The House of Bourbon was a weak ruler for everybody to see given that Napoleon landed with negligible forces and took back power even though he managed to lead France into ruin.
However, you are completely right that the majority of Great Powers did not want to weaken France overly much to not disturb the balance of power. Nevertheless, the principles of restauration were not adhered to completely. For example, nobody thought about reviving Venice, and France did loose more than they had in the Sarre and Palatinate anyway. Another point to consider is that tit effectively came down to what the 5 big powers decided, whereby Prussia was a distinct 5th. If Austria had sided more on the Prussian-Russian side, or if the French would negotiate worse (say Talleyrand dies before the Congress), the peace could easily have been harsher on France.
Thus I think it would be possible that France looses a bit more than they did historically with some minor changes. France over the recent decades even before the Revolution managed to fight for hegemony and sometimes came close. France without Alsace would still be a formidable power, and could be expected to become the strongest continental power soon. Loosing Alsace would therefore not change the balance of power.
On the other side, this is not that much of an issue. As you said France could gain something in what later became Belgium, or something in Western Switzerland, or in Savoy or Nice in exchange for Alsace.
Now assuming Alsace is taken out, the neighbouring states are Prussia, Bavaria and Badenia. If none of these should get it, which I find rather likely, you'd need a POD that necessitates the establishment of a new princedom for a family that lost their home.
The main interesting point here is long-term: how would alsace-Lorraine develop if it was part of the German confederation since 1815? Of course, I'd find it most interesting if it were independent.