Это должно сделать то, что вы хотите в одном запросе
var randomQuestions = questions
.Where(q => categoryIds.Contains(q.CategoryId))
.GroupBy(q = > q.CategoryId)
.Select(grp => grp.OrderBy(_ => Guid.NewGuid()).First())
.ToList();
Это сначала отфильтрует только вопросы по интересующим вас категориям, затем сгруппирует по идентификатору категории и для каждой группы случайным образом выберет один.