I would disagree that AV software is architecturally very difficult. All it needs to do is to check every file on the system against every virus in its database. That's very easy to do; the only complexity really is how to determine if a specific file has a specific virus, and even that is not difficult, you have to know how a virus works and what to look for. There are a couple of other things: you need to check for bootblock viruses, and if possible you should repair or otherwise quarantine the file, being careful not to compromise the user's system by detecting a false positive in a critical system file.
for each file F
for each virus V
does F contain V?
yes: fix or quarantine, alert user
AVG currently has 2,974,423 virus definitions, and across drives C, E and Z I have nearly 450,000 files, not counting the files within archive/zip files. That's 1,338,490,350,000 individual checks it has to perform. That number can be reduced significantly as some viruses only infect some kinds of files, e.g. Excel viruses only need to be checked against .xls files, and some file types (.txt for example) cannot be infected.
AVG also provides a "resident shield" which attempts to detect viruses as they activate, which also helps decrease the amount of filesystem checking an AV program has to do.