Везде в

Console.Out
Console.OutputEncoding
Console.InputEncoding

прописана кодировка 1251, однако в реальности она 866, и соотвественно, сделать вывод русских букв удалось только так

StreamWriter cons = new StreamWriter(Console.OpenStandardOutput(), Encoding.GetEncoding(866));
cons.WriteLine("ТЕКСТ РУССКИМИ БУКВАМИ");
cons.Flush();