Neutral hydrogen mapping of several small, very low column density High Velocity Clouds (HVC), using the Arecibo telescope, is reported. Some were found serendipitously superimposed at distinct velocities on largerHVCs; others were found to comprise the four most isolated low column density sources in the observations of Lockman et al. but proved to be individually much smaller than the Green Bank 140 Foot telescope beam. We call these clouds ``mini-HVC'' to distinguish them from the larger and denser Compact High Velocity Clouds (CHVC). Peak column densities are typically a few X 10^18 cm^-2 averaged over the Arecibo 3.2' beam, and diameters to our detection limit ~ 10^18 cm^-2 range from 9' to 35'. These column densities and angular diameters overlap with those for CHVC, but are typically smaller. We consider three possiblities: (1) that most mini-HVC are related to the Magellanic Stream, (2) that most mini-HVC are part of M31's retinue of CHVC, or (3) that the mini-HVC are simply the low column density tail of the distribution of CHVC. None of these possibilities can be rejected as yet, given the selection biases in our sample. We also discuss controversies about the amount of ionized hydrogen in CHVC and mini-HVC, which may be mainly ionized, and the implications of these small clouds for Lyman Limit Systems.