Blowing cold for a while, then not, is a sign of evaporator freeze-up. The evaporator inside the HVAC box under the dash gets so cold that it freezes up the moisture that condenses on the evaporator coil. Basically, it then becomes a block of ice and won't allow air to flow through. High humidity weather conditions, only running the fan at low speeds, and running AC with windows open, encourage this to happen. Air flow through your vents will be reduced if you have freeze-up. When the AC is turned off for a while, the ice block melts and the AC can work again. Some AC systems respond well to evacuating the system completely and carefully refilling the proper WEIGHT of refridgerant.
From your description, though, your air isn't really that cold, even just a couple of minutes after you start it. You have a good possibility of just being a little low on refridgerant from a slow leak, which is how I would approach it. You could try adding a can of refridgerant to see if it gets colder. Often this works fine.