If you look in the policy's general settings under triggers there might be one of the other options enabled (startup, login, logout etc).

Recurring Check-in is checked. Does that mean the program will install on next check-in?

@Sobchak yes, if that is checked it will install on check-in. If you want a policy to be Self Service only, you need all triggers unchecked and the Self Service tab filled out.

Here is how I have the policy setup:

Under General
Display name = Install Fire Fox
Enabled
Category = Browsers
Trigger = Recurring Check-in
Execution Frequency = Ongoing

Under Packages
Action = Install
FUT
FEU
Distribution Point = Each computer's default distribution point

Under Restart Options
Startup Disk = Current Startup Disk
No User Logged in Action = Restart if a package or update requires it
User logged in action = Restart if a package or update requires it
Delay = 5 minutes

Under Maintenance
Maintenance = Update Inventory

Under Scope
Target = Does not have Firefox (Smart Computer Group)

Under Self Service
Make the policy available in self service = checked
Button Name = Install
Icon = Firefox.png
Catagories = Browsers (Display and Featured)

The goal of this policy is to have Firefox show up in Self Service only on computers that do not have Firefox. The policy should not install Firefox on the computer unless the user runs it from Self Service. Once Firefox is installed on the computer it should be removed from Self Service. If Firefox is removed from the computer Firefox should reappear in Self Service.

Based on this policy setup and goals what needs to be changed?

As @stevewood said, remove all "Trigger" and just have the "Make the policy available in Self Service" under the "Self service" tab.

You only need to remove the Recurring Check-in trigger. Your other settings look fine.

Thank you everyone for all of your help.