It's very hard to understand exactly what is requiring full trust. What
assembly is the error referring to? One thing you can try, is if there's a
configuration entry in the web.config for an assembly group you can try
adding requirePermission="false".

Your best bet though is to first see if the assembly in question can even
run in partial trust. Some absolutely cannot not matter what you try since
they require features that aren't available in partial trust environments.
Test locally by adding <trust  level="Medium" /> to your local config file
(in the system.web section). This will give you a similar environment to
your host and help you debug. You'll need to remove this configuration
before publishing though or you'll receive an error on the host.