I had a similar problem with AutoFixture and EntityFramework a while ago. My solution was to add an extension to AutoFixture, that allows you to build a SUT with a few recursions. That extension has recently been adopted in AutoFixture.
But I understand that your question was not about how to make AutoFixture construct recursive data structures, which is indeed possible, but how to create domain models without recursion.
First, you have tree or graph structures. Here anything but recursion would mean indirection through loose coupled node ids. Instead of defining an association, you would have to traverse the tree query-by-query or cache the whole thing and traverse by node-key lookup, which may be impractical depending on the tree-size. Here it is very convenient to make EF do the work for you.
The other common structure is a two-way navigational structure similar to your user / game scenario. Here it is often not that inconvenient to prune the navigation flow to a single direction. If you omit one direction, say from game to team, you can still easily query all teams for a given game. So: User has a list of games and a list of teams. Team has a list of games. Games have no navigational reference to either. To get all users for a specific game you could write something like:
var users = (from user in DataContext.Users
from game in user.Games
where game.Name == 'Chess'
select user).Distinct()