Picking a random neighbouring cell, but only picking previously-visited ones if there aren't any unvisited
Using straight linq you could get to two iterations over Neighbours, assuming Neighbours is a class and not a struct. 

var neighbour = current.Neighbours.FirstOrDefault(n =&gt; n.DeadEnd) ?? current.Neighbours.Where(n =&gt; !current.Linked(n)).First();


Pretty similar to yours except we using FirstOrDefault to return null if not found and using the ?? to execute the 2nd iteration if it's null.  

If it is a struct then you would need to compare the FirstOrDefault to default.  At that point I would just do the FirstOrDefault and write an If statement on next line comparing it to default.

If you want to do it in one iteration then will need to break out into a foreach loop. The downside is it will be calling the Linked() method even if it will never be used. As needs to store the value just in case it can't find DeadEnd.  

Neighbour defaultValue == null;
foreach (var neighbour in current.Neighbours)
{
    if (neighbour.DeadEnd)
    {
        return neighbour;
    } else if (defaultValue == null &amp;&amp; !current.Linked(neighbour))
    {
        defaultValue = neighbour;
    }
}

return defaultValue;


Without knowing what Linked does - aka does it have side effects or performance issues.  This might not be the best answer.

As you can see from my review there are questions: Neighbours a class or struct?  Should post the source code for Neighbours.  What does Linked method do?  Because of this the code can't fully be reviewed and is not complete.  I would suggest you update your question to get better answers.