I think the question as stated (on 2015-04-20, "Which collation [...]") is not what is meant, given that the accepted answer talks about encoding rather than collation. Let me answer the stated question rather than the intended one, just because I think it is interesting :-)
Wikipedia says "Collation is the assembly of written information into a standard order". In computing, collation has taken on the meaning of "a specification of such an order". In other words, a collation is (or implies) a definition of a three-way comparison function.
I think the short answer is "definitely maybe". At least I'm aware of the following shenanigans:
#!/usr/bin/python
name = u"Jonas K\xf6lker" # \xf6 is o-umlaut
enc = name.encode('utf-8')
assert len(name) == 12 # \xf6 is one character
assert len(enc) == 13 # but two bytes in utf-8
import locale
locale.setlocale(locale.LC_COLLATE, "da_DK.utf8") # works on my machine
long_form = locale.strxfrm(enc)
assert len(long_form) == 38
locale.strxfrm is a function which Returns a string that behaves for cmp locale-aware, that is, it encodes a string such that a byte-by-byte standard lexicographic comparison against another string encoded similarly will produce the same result as comparing strings according to the collation function specified by the locale.
Some observations: in da_DK.utf8, the string ouüö is sorted. In de_DE.utf8, the string oöuü is sorted. Note that len(long_form) == 38 and 38 > 13. (The length is also 38 in de_DE.utf8.)
If your database has an index on some string field, collated according to da_DK.utf8, it may internally be doing something like strxfrm in order to have a simple comparison. (On the other hand, disks are slow. It may be faster to index based on a more compact representation, if a higher per-character comparison cost is more than offset by comparing fewer characters.)
You ask "Does a collation have any influence over a query speed?", to which I'm pretty sure the answer is yes: the "C" (aka "POSIX") collation just compares unicode code point values, whereas the Danish (da_DK.utf8) and German (de_DE.utf8) locales do something more tricky. This will have some impact on query speed, although I suspect it won't be worth worrying about.
"Does the size of a table change depending of the collation?" — I can imagine having an index according to one collation and a different index according to another collation, or just one of such two indices, with some strxfrm-like transformation applied. In that hypothetical scenario, if there are two collations with different size characteristics, the answer is yes.
"which would be the recommended collation?" — That depends on why you would need to sort strings. If it's only to have some canonical way of ordering strings, I'd probably go with "C". If it's to present data to the users in sorted order according the human's expectations, and those expectations are shaped by their culture, and you want the database (and not some other layer) to do the sorting, perhaps you should build one index per collation, i.e. at least one according to da_DK.utf8 for the Danes and one according to de_DE.utf8 for the Germans. I think this might get fairly big fairly quickly, though.
All of this is highly dependent on the inner workings of your database; I think it goes well beyond "standardized" (lol!) SQL. As always, consult the documentation to your specific database system.
