We present ultraviolet (UV) follow-up of a sample of potential dwarf galaxy candidates selected for their neutral hydrogen (HI) properties, taking advantage of the low UV background seen by the GALEX satellite and its large and publicly available imaging footprint. The HI clouds, which are drawn from published Galactic Arecibo L-band Feed Array and Arecibo Legacy Fast Arecibo L-band Feed Array HI survey compact cloud catalogs, are selected to be galaxy candidates based on their spatial compactness and non-association with known high-velocity cloud complexes or Galactic HI emission. Based on a comparison of their UV characteristics to those of known dwarf galaxies, half (48%) of the compact HI clouds have at least one potential stellar counterpart with UV properties similar to those of nearby dwarf galaxies. If they are galaxies, then the star formation rates, HI masses, and star formation efficiencies of these systems follow the trends seen for much larger galaxies. The presence of UV emission is an efficient method to identify the best targets for spectroscopic follow-up, which is necessary to prove that the stars are associated with compact HI. Furthermore, searches of this nature help to refine the salient HI properties of likely dwarfs (even beyond the Local Group). In particular, HI compact clouds considered to be velocity outliers relative to their neighbor HI clouds have the most significant detection rate of single, appropriate UV counterparts. Correcting for the sky coverage of the two all-Arecibo sky surveys yielding the compact HI clouds, these results may imply the presence of potentially hundreds of new tiny galaxies across the entire sky.