Would a smaller satellite be more stable around a smaller planet where the same satellite would not be stable or last around a larger planet?
There are two questions here, a terminological question and one about orbital dynamics and satellite mass.
The International Astronomical Union sometimes establishes criteria for whether astronomical bodies fit into certain classes. Famously, they formalized the definition of "planet" in such a way that Pluto was excluded. I am not aware that they have specified a lower bound for the mass of a natural satellite (so I don't get the bounty since I haven't found documentation either way). But for the rest of this answer, I will define "natural satellite" to be any naturally occurring body in a stable orbit around another body that isn't a star.
With that definition, there is no clear lower bound on the mass of a natural satellite, for the reason given by tuomas. However, the vacuum of space is imperfect and the Earth's atmosphere really just gradually fades away into the interplanetary medium. The smaller an object is, the more it is affected by drag, and this is still true even when the drag is really tiny as is experienced by satellites in orbit. So dust could be expected to last fewer orbits than pebbles.
On an even smaller scale, individual atoms and molecules are considered to be part of the extended atmosphere, either the thermosphere or exosphere, and not treated as satellites. In the thermosphere, there are still enough particle-to-particle collisions to treat it as a gas, so those particles aren't even in orbit themselves since they tend to collide before they make it all the way around. This is true even though the ISS orbits right in the middle of the thermosphere.
But, higher up is the exosphere, where individual atoms hardly ever collide. Some of those are presumably in orbits that last at least a few periods before they collide with another atom, but many others are in the process of falling back toward the thicker atmosphere, or heading outward after getting an especially large random kick from other particles in the thermosphere below. The particles that manage to orbit for a while meet the definition I gave for a natural satellite, but it is certainly true that the word is not generally used for them.
So, there is no lower bound for something to be a natural satellite in the broadest sense. It is possible for a particle to be so small people wouldn't normally refer to it as a satellite, but I don't think there is an exact threshold for that.
As long as the satellite is way smaller than the object it is orbiting, the mass does not make any difference to its orbit.
This is because even while gravitational force depends on product of masses of both objects, the acceleration of orbiting object is this force divided by its mass. Therefore any change to its mass will keep its acceleration and thus velocity and thus orbit about the same as before (as long as there are no significant changes to barycenter the two objects are orbiting; gravitational waves do change things, but only for very extreme cases such as close black hole and/or neutron star binaries)
This will get more complicated if there are more than one satellite orbiting the body, and stability in these cases is often hard to determine (aspects like orbital resonances and phase do matter in these cases)
EDIT: added explanation why mass does not affect orbit