Olives are high in fat, yes, but it's mostly mono-unsaturated fat. You need a little of that anyway, so not the end of the world.

Another option if you get bored with tuna is canned chicken. I know it doesn't sound good, but I mix canned tuna with rice and beans. It can be a little dry, so some salsa works pretty good with it. I like a mustard mix for sandwiches too, like the others said.

Steve