Agnostic PAC sampling lower bound
I now realize that a lower bound has indeed been established by Anthony and Bartlett (see the presentation here). 

Edit 24-Sep-2018. This question has kept me occupied all of these years, and recently, I. Pinelis and I have obtained the exact optimal constant in the agnostic PAC lower bound to appear in Ann. Stat.