By changing the console's input and output encoding settings to Unicode I managed to output the text correctly — at least for all the Czech characters.

// This fixes the problems with displaying non-English characters, at least for Czech. 
Console.InputEncoding = System.Text.Encoding.Unicode;
Console.OutputEncoding = System.Text.Encoding.Unicode;