Aims: With available Virtual Observatory tools, we looked for new M dwarfs in the solar neighbourhood and M giants with high tangential velocities. Methods: From an all-sky cross-match between the optical Tycho-2 and the near-infrared 2MASS catalogues, we selected objects with proper motions μ > 50 mas yr-1 and very red VT - Ks colours. For the most interesting targets, we collected multi-wavelength photometry, constructed spectral energy distributions, estimated effective temperatures and surface gravities from fits to atmospheric models, performed time-series analysis of ASAS V-band light curves, and assigned spectral types from low-resolution spectroscopy obtained with CAFOS at the 2.2 m Calar Alto telescope. Results: We got a sample of 59 bright red high proper-motion objects, including fifty red giants, four red dwarfs, and five objects reported in this work for the first time. The five new stars have magnitudes VT ≈ 10.8-11.3 mag, reduced proper motions midway between known dwarfs and giants, near-infrared colours typical of giants, and effective temperatures Teff ≈ 2900-3400 K. From our time-series analysis, we discovered a long secondary period in Ruber 4 and an extremely long primary period in Ruber 6. With the CAFOS spectra, we confirmed the red giant nature of Ruber 7 and 8, the last of which seems to be one of the brightest metal-poor M giants ever identified.