Simple static ads that are not huge, distracting or obnoxious, that are delivered free of any script or similar code, and all hosted by the first party. Those are the ads I would probably find acceptable.
They should be able to still do this too; presumably they still have an ad department for the dead tree version of things. That means they have the people in place to sell ads and integrate them into their content. Of course, magazine ads don't really fit your "not huge, distracting or obnoxious" requirement but their ad people can evolve too. There's probably even a business in this for websites/companies that don't have dedicated ad departments.