Q:

Does it seem odd to say "I'm in love WITH you?"

I'm brand new to this site so please be kind. It has always struck me as odd to declare one's love for the very 1st time to another by saying, "I'm in love WITH you."  The brief definition I found for WITH was the Oxford one; accompanied by.  Which means both people would be in love with each other.  Why not just say "I love you?"  Does anyone know where the expression came from?

A:

This is a matter of emphasis.
Consider the phrases you mention:

I love you

You might love a variety of food, your dog, your cat, or a person of course.
To say I love you certainly conveys a strong affection, but it doesn't always have to carry the same degree of affection as :

I'm in love with you

The word in creates a sense of being in the middle of this emotion, it's a much stronger sense of love, and idiomatically refers to love between one person and another. The use of the word in creates a stronger intensity of the sense of love.
You might think of other examples of the word in being used, e.g:

I'm in trouble.
I'm in danger.

Just as the word in operates in the above examples, a sense of almost being caught up is created, you are so in love, that this is something happening to you, almost as if you are powerless to choose otherwise, which creates a very strong sense of that feeling and emotion.
Which need not be the case when you simply actively love something or someone.

A:

The OED has a good definition for with in this sense:

After words expressing conduct or feeling towards (a person, etc.).
  In some cases now replaced by other prepositions, e.g. envious of. In expressions of hostile action or feeling, this coincides with 2.

Compare the other expressions under this definition:

have patience with
be annoyed with
be gentle with

Here’s an early example of in love with:

He would talke..of the stories of the Scripture, so sweetely..as I was woonderfully in loue with him.

   Foure Bks. Husbandry, 1577
Also notable is that Shakespeare used the expression in Two Gentlemen of Verona, 1616:

I was in loue with my bed.

