У нас те же проблемы были, правда с девушкой.
И-так, во что играли:
Вдвоём в NeedForSpeed - не нативное, но под wine прёт нормально (она у меня гонщица, даже руль есть)
Вдвоём в Puzzle Quest, но там трабла - порой вылетает =\ (Мультиплеер)
Counter Strike (Steam) - платно (Игра стоит денег)
Left4Dead2 (Steam) - платно (Игра стоит денег)
PlayStation - игры на 2-х, мультиплеер (Bushido Blade, Tekken 2 и т.д.), эмулятор pcsxr
Денди, сега, нинтендо - тоже что и выше. Эмуляторов куча. Почти все поддерживают мультиплеер по инету/локальной сети
Dofus online - это уже ММО.Становится платной при выходе из первого города. Требует подписки.
Spiral Knights - Это уже интереснее. Но тоже ММО. Можно играть и бесплатно, но на данный момент требует знания английского (хотя и есть русскоязычная вики и в планах у разрабов русифицировать приложение)
Бякотанки - c пропатченным wine и урезанными тектурами ведут себя довольно-таки шустренько. А воевать во взводе - одно удовольствие
GameplayFootballPublicBeta08 - футбол, вроде есть возможность на 2-х, правда не тестировалось ещё =\
Warcraft 3 - прекрасно идёт под wine
Ragnarok Battle Offline - можно играть одновременно до 3-х человек. Прекрасный Beat'em up! Нарисованы персонажи просто превосходно! Играется только через Crossover.
Что вспомню - скажу

Кстати выше посоветовали 0a.d - превосходная игра. Есть ещё The Battle for Wesnoth - тоже рекомендую (есть в репах). Там мне кажется частично проще, и сложнее - больше тактике надо уделять внимание

)