Você precisa usar apt.cache e apt.package . Adaptar o exemplo dado para apt.package :
#!/usr/bin/env python2
import apt
cache = apt.Cache()
Games = [pkg for pkg in cache if pkg.section.endswith("/games")]
print("\n".join(map(lambda x: x.name, Games[1:10])))
cache é como um objeto de dicionário, com nomes de pacotes (+ um rótulo de arquitetura opcional) como as chaves. Você usa o método cache.keys() para obter todas as chaves.
Algum exemplo de saída:
funnyboat
berusky2
torcs:i386
glaurung:i386
jigzo-data
balazar3-common
val-and-rick
openyahtzee:i386
mupen64plus-ui-console