I've noticed that when generating random numbers they repeat.
It sounds like you want a random shuffle rather than a random selection. The former will give you a randomized ordering of the set such that there are no repeats until the set is exhausted:
// Untested code
var rand = new Random();
var to_eat = from x in fruits
order by rand.Next()
select x;
foreach (var fruit in to_eat)
{
Console.WriteLine("nom nom " + fruit.Name);
}
Random doesn't mean "no number will be repeated", it means the sequence of numbers will be suitably unpredictable.