I generally go with the context object approach, and pass the context object either to an object's constructor, or to a method -- depending on which one makes the most sense.
The context object pattern can take a few forms.
You can define an interface that has exactly the members you need, or you can generate a sort of container class. For example, when writing loosely-coupled components, I tend to have each component I implement have a matching interface, so that it can be reimplemented if desired. Then I register the objects on a "manager" object, something like this:
public interface IServiceManager
{
public T GetService<T>();
public T RequireService<T>();
public void RegisterService<T>(T service);
public void UnregisterService<T>(T service);
}
Behind the scenes there is a map from type to object, which allows me to extremely quickly assemble a large set of diverse components into a working whole. Each component asks for the others by interface, and the manager object is what glues them together. (If you correctly author your components, you can even swap out one service for another while the process is running!)
One would register a service something along these lines:
class FooService : IFooService { }
// During process start-up:
serviceManager.RegisterService<IFooService>(new FooService());
There is more overhead with this approach than with the flat-interface approach due to the dictionary lookup, but it has allowed me to build very sophisticated systems that can be easily redeployed with different service implementations. (And, as is usual, any bottlenecks I encounter are never in looking up a service object from a dictionary, but somewhere else such as the database.)