Нужно поменять кодировку в консольном приложении на C# для всего приложения, а не для одной строки. Как это сделать?
Console.OutputEncoding = System.Text.Encoding.UTF8; Console.InputEncoding = System.Text.Encoding.UTF8;
Введи вот эти 2 строки в начале запускаемого проекта. Таким образом для консоли ты настраиваешь кодировку ввода/вывода.
UTF8 кодировка содержит в себе больше миллиона различных символов, в том числе и всевозможные кириллические символы (должно хватить на первое время 
)