The C collation is the right choice.
Everything is a bit faster without locale. And since no collation is right anyway, create the database without collation, meaning with C.
It may be a pain to have to provide a collation for many operations. There shouldn't be a noticeable difference in speed between the default collation and an ad-hoc collation, though. After all it's just unsorted data, and collation rules are applied when sorting.
Be aware that Postgres builds on the locale settings provided by the underlying OS, so you need to have locales generated for each locale to be used. More in related answer on SO here and here.
However, as @Craig already mentioned, indexes are the bottleneck in this scenario. The collation of the index has to match the collation of the applied operator in many cases that involve character data.
You can use the COLLATE specifier in indexes to produce matching indexes. Partial indexes may be the perfect choice if you are mixing data in the same table.
For example, a table with international strings:
CREATE TABLE string (
string_id serial
,lang_id int NOT NULL
,string text NOT NULL
);
And you are mostly interested in one language at a time:
SELECT *
FROM string
WHERE lang_id = 5 -- 5 being German / Germany here
AND string > 'foo' COLLATE "de_DE"
ORDER BY string COLLATE "de_DE";
Then create partial indexes like:
CREATE INDEX string_string_lang_id_idx ON string (string COLLATE "de_DE")
WHERE lang_id = 5;
One for each language you need.
Actually, inheritance might be a superior approach for a table like this. Then you can have a plain index on each inherited table containing only strings for a single locale. You need to be comfortable with the special rules for inherited tables, of course.
Best Answer
Generally speaking, one of the Unicode variants is probably the best for broad language support - UTF-8 is going to use less memory per codepoint, and thus will have a slight advantage in any time/space tradeoffs you find yourself in need of making; however, I think there are some of the more esoteric languages/scripts that UTF-8 cannot represent (but I'm not 100% certain of that, I haven't done an exhaustive study on the matter).
This Wikipedia article might be enlightening on the dis/advantages of each.