That's great, so no worries there.
Then I'd personally say everyone's advice is pretty spot on, this isn't going to hurt you just do it and be up front. And tell them both, order in my opinion would be the company you are hired through first and then the agency. Just depends on your relationship with both parties, as I don't think you can go too wrong long as you tell them both timely.
Just remember, if a company doesn't want you there they will walk you out whenever they want, so it is a business transaction as someone else pointed out, but one that is somewhat lopsided generally in favor of the employer. So you are right to be cautious, but don't stress yourself to death, do it and be happy.