No se por qué has descartado el Dota, mi recomendación iba a ir en la línea de un MOBA... Battlerite.
Tienes categorías de liga, casual, y vs IA. El último modo el rival siempre es la máquina, pero tu compañero de combate casi siempre es otro usuario (si no detecta otro usuario buscando partida en unos cuantos segundos te asigna un compañero controlado también por la cpu).
Pero si tienes dudas con el género, mejor esperate un poco, porque cualquier día en este mes o el que viene deja su estado Early Access y entonces será Free to Play.
Recordarte que Tekken 7 sale el próximo día 2 y se puede conseguir barato en algunas webs con la pre-reserva también.
Uno que me gusta mucho es Worms Reloaded (hay más nuevos pero son bastante peores a excepción del arte del último). El problema es que aquí si que puede costar encontrar partida muchas veces ya. Lo bueno... que tiene varios modos de juego (mi preferido es el modo Forts de 2 contra 2, que sin dejar de ser de habilidad le da un toque estratégico que los otros modos no tienen).
Quizás puedas pegarle un vistazo a Torchlight 2 también.
Luego tienes los típicos deportivos que siempre tienen gente online... Por descontado el Counter Strike o Minecraft de turno, etc.