I am setting up load balancing for my Amazon RDS Read Replicas using HAProxy, should I use a m1.large or c1.medium instance type for running HAProxy ?
You might want to look into Elasticache.
If you are determined to use HAProxy then I'd select the instance with a higher memory level when load balancing read replicas.
Are you going to run a cluster of HAProxy so that this is not a single point of failure?
HAproxy works only as a forwarder , and itself it does not do high level processing to balance load, as a front end web server faces load. but it depends upon your level of load, that how what is the threshold level for haproxy, at which it starts consuming high level of CPU. you can start with medium instance, as it is already heavy. run test benchmark to see that how much level of load breaks the threshold of system resources on medium instance. if it fills your requirement, then ok, otherwise go for larger instance. you can run benchmarks with ab(apache benchmark).