I did both of these trips frequently in the 80's and 90's in canoes and sea kayaks, both really nice flatwater trips. Frome what i can recall:
Labyrinth- always did in the late fall, low water. Prefered putting in at Ruby Ranch, although if you want more paddling Green River State park is a good put in that takes you through a day of high plains/semi canyon and I think the shuttle is a bit easier. I don't remember but maybe once in four trips that we ever saw another group and unforntunately it was a local outfitter that felt the need to share our camp at Three Canyon/Trin Alcove.
At low water in the fall there were plenty of nice big beach camps and all the little side canyons offer some kind of a hike with Three Canyon and Horseshoe offering longer hikes and nice camps.
Labyrinth is all BLM except for the take out and we always were able to bring the dog along, which was nice. Not sure if that has changed though.
Stillwater- always did in the spring, all park, no pets. Some kind of permit was required but was somehow offered through Tex's shuttle service (I think?). Lots of lakey flat water and some frequent strong head winds (spring?), great scenery but competition for camps was always tough and fire wood pretty tough to come by.
Hikes up Taylor Canyon and Upheaval Dome were pretty cool, the White Rim Road passes through the area and there is some ORV use. We were able to top out at Water/Shot Canyon which while not being technical climbing, still required some ropes for the safety of some of us not comfortable with exposure. More of a hand hold, but maybe we lost the trail also. Very nice hike though.
I believe Jasper Canyon was off limits as a control area for resource protection and study area but would be worth checking into.
Even after several trips in the area, I don't feel that I have seen much of what is there and would really like to get back there again.
Either trip would be be pretty slow going in a raft but are exceptional canoe and touring kayak trips.