Easiest thing you can do and probably the cheapest is throw a set of plugs in it.... If you have removed a vacuum leak from the list then timing. The video you posted with the Auto tranny is definitely a smooth running engine and the AFR on your interface is showing it's fat but it should have been in Open loop....
I just had the engine dyno tuned and a custom fuel map was created. New plugs were installed. The car has to go back into the shop for some additional work so I'll have them take a look at it.
