pmetis or kmetis?

Which one produces better graph partitions?

RE: pmetis is somewhat better.

pmetis is somewhat better. However, if you want the best possible partitionings, you should use hmetis.