Also if you have any ideas on where to advertise besides bitcointalk (better with links) would be really helpful
I don't have any links like that.
Bitcointalk is probably the best place for advertising services like this, but it needs need for you time to gain trust from customers and that is not easy, so better prepare for some harsh reviews.
I guess you could always try with bitcoin magazines and independent article reviews from people who like privacy for their transactions.