Michael Barber, dean of new initiatives at London University's Institute of Education, sounds almost frightened of the diminutive Scot.
"She's hard as nails," quakes Barber, who first knew Ms Fullick in the late 1980s, when she was (Labour) chair of Newham's education committee, and he held a similar position in Hackney.
"She's a real tough operator who won't be deflected from her task. She expresses her views with great clarity and vigour. She's exactly what Islington needs."
Ms Fullick, displaying a characteristically thick skin, is unabashed by Mr Barber's description: "I'm tough as old boots," she agrees cheerfully.
She is certainly going to need to be, as all eyes will inevitably fall on her once she is ensconced in Labour leader Tony Blair's home borough.
"I know I'll be in the spotlight, and this means my main priority must be to make sure that there are very, very good services," she says.
She intends first to tackle housing. Some 48 per cent of Islington residents are council tenants, many on benefit and living in poverty, she says.
"Islington belies its image. Only a very small area has nice houses occupied by Labour MPs and barristers."
Ms Fullick, 49, was educated at a Catholic comprehensive school in Ayrshire and read history at St Andrews University. She was staff inspector for further and higher education for the former Inner London Education Authority before becoming Lewisham's education director in 1988.
She had a brief encounter with media exposure in 1992 when the BBC produced a fly-on-the-wall documentary, Town Hall, during which she was asked to explain a possible Pounds 10 million overspend in her department.
Demonstrators outside the town hall could be heard shouting "Leisha out, Leisha out!" but she survived calls from headteachers and parents for her resignation.
Despite her undoubted ability to tough it out in a crisis, there appears to be a soft centre beneath the iron exterior.
Dan Taubman, assistant secretary for the lecturers' union NATFHE, has known Ms Fullick since the two were community education workers for ILEA more than 20 years ago.
At the time she was active in the Association of Adults in Continuing Education, which later became part of NATFHE.
"She's very capable, but also warm and likes a good laugh," he says. Another friend, who prefers to be nameless, says she is not the type to burst into tears at a meeting, but can get upset and tends to reflect privately on what has happened.
She relies on a small number of close friends and family members for support, he adds.
"She's not impervious to what is going on around her. She's quite sensitive about things." It is nice to know even chief executives are human.
Ms Fullick says people have asked why she wanted the new job - which she will begin in June - given her education background. But she believes her expertise in this area will be an advantage.
"One of my priorities is urban regeneration. Inner-city areas are only going to be improved by increasing the skills of the population. Linking community regeneration to adult learning is something I've always been interested in," she says.
Speculation about potential clashes between her and Islington's chief education officer Dr Hilary Nicolle, a traditional, former grammar school head, is misplaced, she insists.
She has no intention of encroaching on Dr Nicolle's territory. "I'm not coming to Islington to run education. Hilary runs it," she adds firmly. Watch this space.