My first gun was a Glock 17 and I have never owned anything smaller, so not all people need to start out small.
My wife is a petite 125lb 5'8" model and her first gun was a polymer framed UltraStar .40. It is the hardest kicking handgun in our house including my .45's. She loves it. She has never been intimidated by it. Have your wife wear ear plugs AND muffs so the noise doesn't scare her. Have her shoot the gun for feel before letting her stress about where she hits (just some advice that has worked for me).
I am not saying that the .22 idea is a bad one, but it is not the only one. Recently I borrowed my mom's .22 and when I go shooting with my wife she has no interest in shooting it. I think she must have that same drive that many shooters do, and she gets that rush from shooting a "real" gun, not wanted to waste her time with a peashooter (no offense to small-gun-lovers out there, but you big-bore lover's know what I mean...there is a rush that comes with mastering and shooting a larger caliber).
On the other hand, my wife and I went and rented a Kahr 9mm and she is in love! The recoil and index were far less than her .40 and she could shoot about twice as fast, accuratly. (It's rather intimidating, she is getting fast and accurate...maybe I shouldn't get her that Kahr
).
The steel Kahr 9mm is a bit heavier than the polymer UltraStar and the barrel index is lower. Also, the handle fits like a dream. I cannot give enough praise to the Kahr 9mm after shooting it. What a great gun!!! Particularly designed for people with small hands (I had a little trouble with that, but it is a great CCW piece).
I am going to get my wife the "Lady Kahr" 9mm, which is the "full sized" version (still very small) with no changes other than a lighter recoil spring. My wife had a little trouble getting the slide back on the regular Kahr 9mm. She is a trooper at heart, but she is still physically weak and can't even get my Glock 17 slide back (a relatively light spring with a good solid grip area on the slide). The Lady Kahr 9mm is the perfect gun for her.
Another reason I opted for the Kahr 9mm is that no matter how many times we go shooting, my wife still takes a second to remember how to use the slide mounted saftey/decocker on the UltraStar. That extra second could cost her her life when she needs to defend herself with that gun NOW. I decided to get her a Kahr 9mm because it has no controls - just pull the trigger.
JMHO,
thaddeus