А как в Линухе вообще менять разрешение экрана и частоту?

make Xconfigurator

Для framebuffer - fbset
В не-framebuffer консоли можно попробовать SVGATextMode

В X-ах - man XF86Config
Для framebuffer - fbset
Для не-framebuffer консоли - SVGATextMode

А как для обычно текстовой консоли? Или чем (не-X) ее можно заменить?

А никак, она обычная и таких веще не знает.
Если только ты пзушку карточки переделаеш )

я тоже сталкивался с этим - а просто надо зайти Mandrake Conf или что-то на подобее этого - а там зайти на хардваре - и смотреть Сhange resolution (названия могут чуть отличатся - по памяти пишуб но выйти на это можно через главное меню типа ПУСК)