The mutual efforts of joining art and science have been an important source of innovation in many fields throughout history. In this article, we investigate the relatively common origins, differences, and similarities between the Interactive Art and Human-Computer Interaction (HCI) areas of knowledge. We also investigate what kind of human-computer interactions are sought by artists or emerge in Interactive Art examples, as well as what kind of frameworks, evaluation criteria or methodologies are reported in the literature to support the design and evaluation of Interactive Art. As a result of our analysis of Interactive Art examples found in the literature and beyond, we derived four genres of dialogue that emerge naturally or are stressed by authors: visual, embodied, tangible and social. These genres, albeit not comprehensive, can inspire the design of novel forms of interaction in computational systems with or without artistic intent. Moreover, frameworks, evaluation criteria, and methodologies may allow a cross-pollination between Interactive Art and HCI. While interactive artists may provide novel ways to look at the design and evaluation of interactive systems, these artists may also benefit from appropriating traditional HCI methods, tools, and technologies for new purposes. Lastly, we draw on our findings and learned lessons to outline a research agenda with the main objectives of 1) encouraging Interactive Art research, 2) studying Interactive Art examples, 3) practicing Interactive Art design and evaluation, and 4) designing Interactive Art for all.