How are non-glucose sugars metabolized in the body?
Where is this occurring in the body?

Almost totally in the liver.

To leave the liver as a sugar, it would have had to been converted to glucose, right?

Correct, but it's not a direct conversion.
Fructose is metabolized almost completely in the liver in humans, and is directed toward replenishment of liver glycogen and triglyceride synthesis...
...Increased concentrations of DHAP and glyceraldehyde-3-phosphate in the liver drive the gluconeogenic pathway toward glucose-6-phosphate, glucose-1-phosphate and glycogen formation. It appears that fructose is a better substrate for glycogen synthesis than glucose and that glycogen replenishment takes precedence over triglyceride formation. Once liver glycogen is replenished, the intermediates of fructose metabolism are primarily directed toward triglyceride synthesis.
So, Fructose is almost entirely made into something else first, and then that something (Glycogen or the Glycerol from triglycerides) gets broken down into Glucose or an intermediate.
Fructose stays in the liver because Fructokinase has a pretty low Km (0.5 mM) compared to Glucokinase (12mM) for Fructose, so almost all of the Fructose that enters the liver is phosphorylated into F1P - which cannot leave.