I have a affinity towards Olde Towne, but that may be related to my previous home. Closer to Alum Creek, there are the amenities of Franklin Park, Wolfe Park (which is also a dog park,) the bike path and Jeffrey Park and Mansion all within walking distance. Franklin and Oak Streets are particularly safe and well kept in-between Fairwood and Rhoads. There is a great suspension footbridge that connects Franklin Park to Wolfe Park too (this is also the Alum Creek Bike Path that goes from Westerville to Three Creeks Park.) This area is technically not Olde Towne, but Franklin Park South but if you value great parks, this is the best area in Columbus. However, crime is going to be a concern west of Morrison and south of Bryden.
Maybe even nicer than Franklin Park South and offering many of the same amenities is Woodland Park. Clifton, Long Street and Woodland in particular have some beautiful homes. Make sure to check out the mansions on Clifton on the small boulevard section and the homes across the street from the Mansion School on Long. Crime goes up as you get closer to the hospital, further north and in the flood plain by the railroad tracks. Both of these areas proximity to Bexley would be nice if you choose to go to synagogue? The disadvantages of these areas are slightly elevated crime and not much in terms of businesses in walking distance other than the conservatory. However, with the conservatory taking over the maintenance of Franklin Park, it will probably soon be nicer than Schiller and Goodale.
If walkability is more important, I would try to get as close to Engine House No. 12 as possible (the area bounded by 20th, Broad, Parsons and Bryden.) Black Creek Bistro is moving to the engine house and I believe this will really be a premier destination restaurant and do what Rigsby's did for the Short North. There aren't any vacancies in that section of Parsons and with a new pizza joint going in on Oak, I only see it getting better. There is a lovely community garden at the corner of Oak and Garfield that is worth taking a look at. Another positive is this is a very safe area too.
The higher crime areas seem to be corridors of Ohio, Kelton and Miller but even there it can be block to block. The area bounded by Long and Broad (NoBo) I feel is rather safe and has some nice housing stock but is lacking many of the amenities I mentioned before. In that area, I really love Eastwood and Miami. I personally wouldn't buy north of Long unless you are on Hamilton. There are just too many vacant lots and houses there for me.
There is always this gem too ;) Do you two have a price range you are looking in? I'd talk with Joe Peffer. He lives in the area.