As a native speaker, it sounds grammatically correct to me. However, usage would depend on the situation.
If you run into a potential co-worker, I would say "Oh! I just applied for a position at your company/in your department" or "I recently applied to here" (if you are THERE at the moment).
I don't have any problem with just - just indicates very recently, to me it does not sound less formal or anything like that. I'm a librarian and I've used it in similar contexts.
I wouldn't, however, say "with you" because that's most likely not true. That is, you did not apply to work solely with that person - you applied to work at the company with everyone that works there. It sounds odd to single out one person like that. Unless, off course, you're talking to a close friend that works for A company and you say "I just applied to work with you!" - which would be taken in joking manner, mostly likely.