Ubuntu – Packages were automatically installed and are no longer required

All Ubuntu ISO ([UKLX]buntu/Ubuntu-gnome) comes with .manifest file that contains the list of all pre-installed packages in the ISO. You can find those manifest files in the same download dir as those ISO on any Ubuntu ISO mirrors. Take the list of available Ubuntu releases as an example; if you have Trusty 64-bit for example, the manifest link would be http://releases.ubuntu.com/trusty/ubuntu-14.04.2-desktop-amd64.manifest.

So once you have this file, just compare the package listing in it against the listing of all installed packages in your Ubuntu using comm command

$ curl -O http://releases.ubuntu.com/trusty/ubuntu-14.04-desktop-amd64.manifest
$ comm -23 <( dpkg --get-selections | awk '$2 ~ /^(install|hold)/ { print $1 }' | sort ) \
        <( awk '{ print $1 }' ubuntu-14.04-desktop-amd64.manifest | sort )

To explain what the comm does, it takes input from 2 files - first one supplies the list of all currently installed packages and the second one the manifest file. The -3 opt suppresses lines that both files have and -2 suppresses lines that only the second file (manifest file, that is) has. So in the end your output contains only lines that only file one has and that gives you packages that you installed manually since the OS was installed.

So there you have it.

Edit

If you'd also like to see the package version next to package name in the output, as Slyvain Pineau pointed out, pipe the comm command above to xargs dpkg-query -W -f='${binary:Package} ${Version}\n' so it becomes

$ comm -23 <( dpkg --get-selections | awk '$2 ~ /^(install|hold)/ { print $1 }' | sort ) \
           <( awk '{ print $1 }' ubuntu-14.04-desktop-amd64.manifest | sort ) | \
           xargs dpkg-query -W -f='${binary:Package} ${Version}\n

Or alternatively, with awk entirely, This too give the same result as command above

awk 'FNR==NR {arr[$1];next} !($1 in arr) { print $0 }' ubuntu-14.04-desktop-amd64.manifest <( dpkg-query -W -f='${binary:Package} ${Version}\n' )

See this link for explanation on how the awk cmd work