The smallest (circular) object that is possible to see from space would have to have at least (bare minimum):
cca. 120 meters
in diameter. But this would work only if the object was distinguishable from the terrain around and the conditions were perfect. It would have to be in a unnatural color - red, for example - and may have to be a strong light source (the ISS and most stars are visible from Earth only because they shine really bright), but making your object shine would be a "cheat", as you said.
The maths:
An average man's eye can distinguish objects that cover up more than about $0.0165$ or $\frac{1}{60}$ degrees. If we define $x$ as the minimal size, we get this image:

If we cut it down, we get:

That means that $\tan(0.00825°) \approx \frac{\frac{x}{2}}{413}$ and from that we can get that:
$x \approx 2×413×0.000144 \approx 0.120km$
Enough math, let's go real: An object would have to be much bigger than 120m in order to be visible from space. For example, the biggest pyramid of Giza takes up 440×440m up, but has the same color as it's surroundings, thus being "invisible" from space. If people manage to color the pyramid(s) red or brown or a similar visible colors, they would be visible.

