para windows pilla el codec COREAVC PRO, si no te tira bien con ese codec los videos con compresion H264/x264 olvidate entonces de los vídeos en alta definición
En linux los mas usados son Mplayer con Smplayer como menu, gmplayer (mplayer con menu propio, lo uso cuando me da problemas Smplayer), Xbmc (reproductor en plan mediacenter) y VLC.
Lo de la grafica te lo habran preguntado por que las nuevas graficas de Nvidia aceleran la descompresion de video (asi un PC que antes no tiraba apenas de 720p ahora tira de 1080p y el CPU ni se usa casi)
De todas formas hay una version de Mplayer modificada que aprovecha algo mas los CPU duales en linux, Mplayer-mt creo que era, tambien hay comandos para el mplayer normal que mejoran el rendimiento. Vamos hay posibilidades, incluso un mplayer modificado para aguantar el codec CoreAVC de windows, si vas mirando encontras todas estas opciones y mas.