That GC a pretty big caveat! Combined with the fact that unreferenced objects are never pushed.
reflog is like undelete in filesystems, it's a probabilistic accident recovery mechanism for an individual computer (repo checkout in this case) that you can try to use if you don't have backups.
In any case, git garbage collection isn't a common phenomenon. It usually triggers every few weeks, even in repos with high activity. The chance of hitting a GC that deletes an untracked commit you need is extremely small.
A rebase does not destroy information. It creates new commits and moves the branch head to a different spot on the graph.
The reason git is seen as painful is because you can't claim expertise until you develop the ability to form a mental map of the graph. But once you do this the lights turn on and everything starts to make sense.
This is why the mantra "commit early and often" still holds. The more experienced git user will tell the newer people this, so when they come with a mess it will always be recoverable.