I like the format you proposed where objects matching host and hosthow are combined into sentences. Also I agree it's best to only color and link each object once which gives the reader a sense of how many things exist in the room even if they are mentioned more than once for hosting.
When there are multiple objects matching host and hosthow:
(also, ) {hosthow} {host} is {obj1}, {obj2}..., and {objn}.
or
You (also) see/notice/etc {obj1}, {obj2}..., and {objn} {hosthow} {host}.
But when host matches but hosthows are different you can combine them like this:
You (also) see/etc {obj1} {hosthow1} {hostname}, {obj2} {hosthow2} {host's $himher}..., and {objn} {hosthown} {host's $himher}.
I also like the cycle approach for variation. Random would make the look change how it describes things even if nothing changed. Cycle can prevent that. To keep it from being the same from room to room you can set the initial cycle option to $loc mod numofoptions (I don't know what the modulus operator is in perl). Then you have variety from room to room, but returning to a certain room is familiar.
That's all I can think of for now. My girlfriend kept me up rather late last night.