1. He is of medium height.

2. He is of average weight.

3. He has long wavy hair.

4. She has short straight blond hair.

5. She has medium-length wavy blonde
hair.

(Are they all grammatical? What about omitting 'of' in #1 and #2?)

Grammatically, you need the "of" in 1 and 2 because "he" is not a height!

In 3, 4, and 5, you need commas for the coordinating adjectives:
http://grammar.ccc.commnet.edu/grammar/commas.htm Scroll down and read #5.

Where will you put commas in those three sentences?

They are all grammatical, but the last three need commas. See the below:

6. Use commas to separate two or more coordinate adjectives that describe the same noun. Be sure never to add an extra comma between the final adjective and the noun itself or to use commas with non-coordinate adjectives.

Coordinate adjectives are adjectives with equal ("co"-ordinate) status in describing the noun; neither adjective is subordinate to the other. You can decide if two adjectives in a row are coordinate by asking the following questions:

Does the sentence make sense if the adjectives are written in reverse order?

Does the sentence make sense if the adjectives are written with and between them?

If you answer yes to these questions, then the adjectives are coordinate and should be separated by a comma. Here are some examples of coordinate and non-coordinate adjectives:

He was a difficult, stubborn child. (coordinate)
They lived in a white frame house. (non-coordinate)
She often wore a gray wool shawl. (non-coordinate)
Your cousin has an easy, happy smile. (coordinate)
The 1) relentless, 2) powerful 3) summer sun beat down on them. (1-2 are coordinate; 2-3 are non-coordinate.)
The 1) relentless, 2) powerful, 3) oppressive sun beat down on them. (Both 1-2 and 2-3 are coordinate.)

Obtained from:

http://owl.english.purdue.edu/owl/resource/607/02/

I hope this helps. Thanks for asking.

3. He has long, wavy hair.

4. She has short, straight, blond hair.

5. She has medium-length, wavy, blonde
hair.

(Are they OK?)

Yes, good job. All are correct! =)

Yes, all of the sentences you've provided are grammatically correct. However, when it comes to omitting the word "of" in sentences 1 and 2, it would slightly change the meaning and create a less formal tone.

1. "He is of medium height." - This sentence is grammatically correct and commonly used when describing someone's physical stature or appearance. The phrase "of medium height" means that the person's height is average or falls within the middle range. Omitting the word "of" and saying "He is medium height" could still be understood, but it may sound more informal or colloquial.

2. "He is of average weight." - This sentence is also grammatically correct and used to describe someone's weight in relation to what is considered typical or within the range of normal. Similarly, omitting "of" and saying "He is average weight" would convey a similar meaning, but the sentence would sound less formal.

In both sentences, using "of" helps to convey the idea that the height and weight are characteristics or qualities possessed by the person being described.