The answer is, as always, “it depends”. It depends on how big the returned collection will be. It depends on whether the result changes over time, and how important consistency of the returned result is. And it depends very much on how the user is likely to use the answer.
First, note that you can always get a Collection from a Stream, and vice versa:
// If API returns Collection, convert with stream()
getFoo().stream()...
// If API returns Stream, use collect()
Collection<T> c = getFooStream().collect(toList());
So the question is, which is more useful to your callers.
If your result might be infinite, there’s only one choice: Stream.
If your result might be very large, you probably prefer Stream, since there may not be any value in materializing it all at once, and doing so could create significant heap pressure.
If all the caller is going to do is iterate through it (search, filter, aggregate), you should prefer Stream, since Stream has these built-in already and there’s no need to materialize a collection (especially if the user might not process the whole result.) This is a very common case.
Even if you know that the user will iterate it multiple times or otherwise keep it around, you still may want to return a Stream instead, for the simple fact that whatever Collection you choose to put it in (e.g., ArrayList) may not be the form they want, and then the caller has to copy it anyway. If you return a Stream, they can do collect(toCollection(factory)) and get it in exactly the form they want.
The above “prefer Stream” cases mostly derive from the fact that Stream is more flexible; you can late-bind to how you use it without incurring the costs and constraints of materializing it to a Collection.
The one case where you must return a Collection is when there are strong consistency requirements, and you have to produce a consistent snapshot of a moving target. Then, you will want put the elements into a collection that will not change.
So I would say that most of the time, Stream is the right answer — it is more flexible, it doesn’t impose usually-unnecessary materialization costs, and can be easily turned into the Collection of your choice if needed. But sometimes, you may have to return a Collection (say, due to strong consistency requirements), or you may want to return Collection because you know how the user will be using it and know this is the most convenient thing for them.
If you already have a suitable Collection “lying around”, and it seems likely that your users would rather interact with it as a Collection, then it is a reasonable choice (though not the only one, and more brittle) to just return what you have.