A normal holodeck actually does have physicality - or rather, it can. When a human (or other physical being) enters the Holodeck, it has to make some of the features 'solid'. From Memory Alpha's "Holodeck" entry:
A holodeck combines elements of transporter technology with that of replicators, by generating actual matter, as well as projecting force fields to give the objects the illusion of substance.
It goes into further detail, to remind us that "Matter and energy are interchangeable as such objects created on the holodeck can be either matter or energy"
The interesting thing to note is that replicators can be invoked in a holodeck simulation to create real things, such as food. I thought this example was in that article, but I'm not seeing it, so I'll summarize it here: Someone wants to eat, say, an apple, they may load an apple orchard program. The holoprojector creates holograms of the trees. As they approach, they touch the tree, and at that moment, the holoprojector creates a solid force field so that it feels real to the user. Then they reach up and pluck an apple. At that moment, the holoprojector invokes the replicator to replicate an actual apple, so that the user can safely eat it.
Additionally, it must be remembered that people in the Holodeck are actually in an enclosed room. All the movement and subjective space between people (if it's larger than the room's space) is an illusion. If someone approaches the actual wall of the holodeck when there isn't one in the program, they will be moved via a force field "treadmill" (according to Memory Alpha).
Now, Memory Alpha also says this about holoprograms, referencing the very episode you did:
A holodeck also has the ability to create holodecks within holodecks, and holodeck programs are able to be saved to a tech cube that can be inserted into an enhancement module to form an optronic data core with information to "last a lifetime". (TNG: "Ship in a Bottle")
Moriarty and all the characters saved to the tech cube are programs. They don't need force fields or replicated objects, and in fact, the tech cube cannot have them. Nor do they actually exist in a holodeck room. So there is no physicality, as Data says.