Here are some tips you should follow if you want to get the maximum performance out of a Linq query parallelized with PLinq (at least with upcoming Mono version) :
Use an indexed data structure as your source like an array, a list or anything which implements the generic IList<T> interface.
Never use an ordering operator like OrderBy and never assume that the query should be ordered.
The overloads of some operator that provide an index integer are also to avoid.
The syntactic sugar operators based on Aggregate like Min, Max, Average, etc... can also be used.
If you can manage it in your code, use the ForAll method with an action delegate instead of iterating over the query with
Of course, forbid any synchronization (locks, semaphore, ...) inside the operator selectors/predicates. The purest your lambdas are, the better.
The functions used with operators should be predictive and stable i.e. not depend on something uncertain time-wise like a network call and should yield approximately the same execution time with each input.
Sure, this is not always possible but if it is, it does prevent the engine from having to repeatedly balance the query execution itself.
The PLinq MSDN page contains some additional tricks and explanations if you are interested.